树形DP

前提：如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头节点的子树在S规则下的每一个答案，并且最终答案一定在其中。

二叉树节点间的最大距离问题

从二叉树的节点a出发，可以向上或者向下走，但沿途的节点只能经过一次，到达节点b时路径上的节点个数叫作a到b的距离，那么二叉树任何两个节点之间都有距离，求整棵树上的最大距离。

分析：

1. 当前节点X不参与的情况：当前最大距离可能来着左树的最大距离，右数的最大距离。
2. 当前节点参与的情况下：左树最远节点，到右树最远节点。左树高 + 1（自己）+ 右树高。
3. 三个值求最大值就为整棵树上的最大距离。对于每个节点需要2个信息：最大距离和树的高度。

public class Morris {

    // 二叉树节点
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    // 返回信息
    public static class Info {
        public int maxDistance; // 最大距离
        public int height;      // 高度

        public Info(int dis, int h) {
            maxDistance = dis;
            height = h;
        }
    }

    // 递归函数 返回以x为头的整棵树 的 信息
    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int p1 = leftInfo.maxDistance;
        int p2 = rightInfo.maxDistance;
        int p3 = leftInfo.height + 1 + rightInfo.height;
        int maxDistance = Math.max(p1, Math.max(p2, p3));               // 最大距离
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;   //树的最大高度
        return new Info(maxDistance, height);
    }

    public static int maxDistance(Node head){
        return process(head).maxDistance - 1;
    }
    
    public static void main(String[] args) {
        Node head1 = new Node(1);
        head1.left = new Node(2);
        head1.right = new Node(3);
        head1.left.left = new Node(4);
        head1.left.right = new Node(5);
        head1.right.left = new Node(6);
        head1.right.right = new Node(7);
        head1.left.left.left = new Node(8);
        head1.right.left.right = new Node(9);
        //返回以head1为头节点的树的最大距离
        System.out.println(maxDistance(head1));
    }

}

树形DP套路

1. 以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性。
2. 根据第一步的可能性分析，列出所有需要的信息。
3. 合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构
4. 设计递归函数，递归函数是处理以X为头节点的情况下的答案。
   包括设计递归的basecase，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构这四个小步骤

派对的最大快乐值

问题

公司的每个员工都符合Employee类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有任何下属的基层员工(subordinates列表为空)，除基层员工外，每个员工都有一个或多个直接下级。

class Employee {
	public int happy; //这名员工可以带来的快乐值
	List<Employee> subordinates; //这名员工有哪些直接下级
}

这个公司现在要办party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下规则。

1. 如果某个员工来了，那么这个员工的所有直接下级都不能来
2. 派对的整体快乐值是所有到场员工快乐值的累加
3. 你的目标是让派对的整体快乐值尽量大
4. 给定一棵多叉树的头节点boss，请返回派对的最大快乐值。

解题

解题思路：当一棵树头节点为x时，如图所示，可分为两种情况：
①当x参与：则maxHappy = x(乐) + a树不来的快乐值 + b树b不来的快乐值
②当x不参与：则maxHappy = 0 + max(a树a来的快乐值, a树a不来的快乐值) + max(b树b来的快乐值, b树b不来的快乐值)

代码

public class PartyMaxHappy {

    class Employee {
        public int happy; //这名员工可以带来的快乐值
        List<Employee> subordinates; //这名员工有哪些直接下级
    }


    class Info{
        public int comeMax;
        public int notComeMax;

        public Info(int comeMax, int notComeMax) {
            this.comeMax = comeMax;
            this.notComeMax = notComeMax;
        }
    }


    public int maxHappy(Employee boss) {
        Info headInfo = process(boss);
        return Math.max(headInfo.comeMax, headInfo.notComeMax);
    }

    public Info process(Employee e){
        if (e.subordinates.isEmpty()){
            return new Info(e.happy, 0);
        }

        int eCome = e.happy;
        int eNotCome = 0;
        for (Employee employee : e.subordinates){
            Info nextInfo = process(employee);
            eCome += nextInfo.notComeMax;
            eNotCome += Math.max(nextInfo.comeMax, nextInfo.notComeMax);
        }
        return new Info(eCome, eNotCome);
    }
}

morris遍历

线索二叉树

morris是二叉树遍历算法的进阶算法，morris遍历可以将非递归遍历中的空间复杂度O(n)降为O(1)。从而实现时间复杂度为O(N)，而空间复杂度为O(1)的精妙算法。

假设来到当前节点cur,开始时cur来到头节点位置

1. 如果cur没有左孩子，cur向右移动(cur = cur.right)
2. 如果cur有左孩子，找到左子树上最右的节点mostRight:
   1. 如果mostRight的右指针指向空，让其指向cur,
      然后cur向左移动(cur = cur.left)
   2. 如果mostRight的右指针指向cur，让其指向null,
      然后cur向右移动(cur = cur.right)

3) cur为空时遍历停止

遍历结果为 1(左树最右为5)， 2（左树最右为2）， 4 （当来到4的时候左子树为空，向右移动）2, 5, 1, 3, 6, 3, 7

一些位置走了2遍，通过判断左树上最右节点的右指针是否指向自己，来判断是否已经遍历过自己。

代码

public void mirrors(Node head) {
    if (head == null) {
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            // 找到左子树最右节点， 并且这个节点的右指针不指向自己
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }

            // 首次遍历
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else { //mostRight.right == cur
                mostRight.right = null;
            }
        }
        cur = cur.right;
    }
}

对于每个节点虽然遍历了2编，但是所遍历的节点它们并不重复，固时间复杂度为O(n)

先中后序遍历

1. mirrors遍历的先序遍历，出现一次的直接打印，出现两次的只打印第一次

   public void mirrorsPre(Node head) {
       if (head == null) {
           return;
       }
       Node cur = head;
       Node mostRight = null;
       while (cur != null) {
           mostRight = cur.left;
           if (mostRight != null) {
               // 找到左子树最右节点， 并且这个节点的右指针不指向自己
               while (mostRight.right != null && mostRight.right != cur) {
                   mostRight = mostRight.right;
               }
   
               // 首次遍历
               if (mostRight.right == null) {
                   // 出现2次的
                   System.out.println(cur.value);
                   mostRight.right = cur;
                   cur = cur.left;
                   continue;
               } else { //mostRight.right == cur
                   mostRight.right = null;
               }
           }else{
               // 出现一次的
               System.out.println(cur.value);
           }
           cur = cur.right;
       }
   }

2. 中序遍历：出现一次的直接打印，出现两次的只打印第二次

   public void mirrorsIn(Node head) {
       if (head == null) {
           return;
       }
       Node cur = head;
       Node mostRight = null;
       while (cur != null) {
           mostRight = cur.left;
           if (mostRight != null) {
               // 找到左子树最右节点， 并且这个节点的右指针不指向自己
               while (mostRight.right != null && mostRight.right != cur) {
                   mostRight = mostRight.right;
               }
   
               // 首次遍历
               if (mostRight.right == null) {
                   // 出现2次的
                   mostRight.right = cur;
                   cur = cur.left;
                   continue;
               } else { //mostRight.right == cur
                   mostRight.right = null;
               }
           }
           System.out.println(cur.value);
           cur = cur.right;
       }
   }

3. 后序遍历：只判断节点是不是第二次出现，若是逆序打印左树的右边界，整个过程之后，打印整颗子树的右边界。

   public void mirrorsPost(Node head) {
       if (head == null) {
           return;
       }
       Node cur = head;
       Node mostRight = null;
       while (cur != null) {
           mostRight = cur.left;
           if (mostRight != null) {
               // 找到左子树最右节点， 并且这个节点的右指针不指向自己
               while (mostRight.right != null && mostRight.right != cur) {
                   mostRight = mostRight.right;
               }
   
               // 首次遍历
               if (mostRight.right == null) {
                   // 出现2次的
                   mostRight.right = cur;
                   cur = cur.left;
                   continue;
               } else { //mostRight.right == cur
                   mostRight.right = null;
                   printEdge(cur.left);
               }
           }
           printEdge(cur.left);
           cur = cur.right;
       }
   }
   
   public void printEdge(Node x){
       Node tail = reverseEdge(x);
       Node cur = tail;
       while (cur != null){
           System.out.println(cur.value);
           cur = cur.right;
       }
       reverseEdge(tail);
   }
   
   // 相当于链表反转
   private Node reverseEdge(Node from) {
       Node pre = null;
       Node next = null;
       while (from != null){
           next = from.right;
           from.right = pre;
           pre = from;
           from = next;
       }
       return pre;
   }

判断一颗树是不是搜索二叉树

public boolean isBST(Node head) {
    if (head == null) {
        return true;
    }
    Node cur = head;
    Node mostRight = null;
    int preValue = Integer.MIN_VALUE;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            // 找到左子树最右节点， 并且这个节点的右指针不指向自己
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }

            // 首次遍历
            if (mostRight.right == null) {
                // 出现2次的
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else { //mostRight.right == cur
                mostRight.right = null;
            }
        }
        // 是否是递增
        if (cur.value <= preValue) {
            return false;
        }
        preValue = cur.value;
        cur = cur.right;
    }
    return true;
}