树形dp套路

在做树结构的题目中，如果求解规则可以分为，以某个节点为子树，先向左要数据，再向右要数据，最后返回总数据，我们就可以使用该套路。

递归进行遍历

public static void QTraverse2(Point tree) {
        if (tree == null) {
            return;
        }
        System.out.println("先序");
        QTraverse2(tree.left);
        System.out.println("中序");
        QTraverse2(tree.right);
        System.out.println("后续");
        
    }

非递归进行遍历

//非递归前序遍历  使用栈
   public static void QTraverse1(Point tree) {
       Stack<Point> stack = new Stack<>();
       stack.add(tree);
       while (!stack.isEmpty()) {
           Point pop = stack.pop();
           System.out.print(pop.value + " ");
           if (pop.right != null) {
               stack.add(pop.right);
           }
           if (pop.left != null) {
               stack.add(pop.left);
           }
       }
   }

   //非递归中序遍历
   public static void ZTraverse1(Point tree) {
       Stack<Point> stack = new Stack<>();
       stack.add(tree);
       while (!stack.isEmpty()) {
           while (tree.left != null) {
               stack.add(tree.left);
               tree = tree.left;
           }
           Point pop = stack.pop();
           System.out.print(pop.value + " ");
           if (pop.right != null) {
               stack.add(pop.right);
               tree = pop.right;
           }
       }
   }

   //非递归后序遍历
   public static void HTraverse1(Point tree) {
       Stack<Point> stack = new Stack<>();
       Stack<Point> stack1 = new Stack<>();
       stack.add(tree);
       while (!stack.isEmpty()) {
           Point pop = stack.pop();
           stack1.add(pop);
           if (pop.left != null) {
               stack.add(pop.left);
           }
           if (pop.right != null) {
               stack.add(pop.right);
           }
       }
       while (!stack1.isEmpty()) {
           System.out.print(stack1.pop().value + " ");
       }
   }

宽度遍历

//宽度遍历  也就是将二叉树一行一行的遍历
    public static void WideTraverse(Point tree) {
        //关键就是我们需要知道我们遍历节点的层数  我们可以使用LinkedList(Java提供的队列 先进先出)
        LinkedList<Point> list = new LinkedList<>();
        list.add(tree);
        while (!list.isEmpty()) {
            Point pop = list.pop();
            System.out.print(pop.value + " ");
            if (pop.left != null) {
                list.add(pop.left);
            }
            if (pop.right != null) {
                list.add(pop.right);
            }
        }

    }

求二叉树的宽度

//求二叉树的宽度  也就是求出整棵树哪一行的节点最多  使用map和栈（不灵活）
    public static void GetWid(Point tree) {
        HashMap<Point, Integer> map = new HashMap<>();
        map.put(tree, 1);
        Stack<Point> stack = new Stack<>();
        stack.add(tree);
        int flor = 0;
        while (!stack.isEmpty()) {
            Point pop = stack.pop();
            //从栈中pop出的元素的层数
            Integer num = map.get(pop);
            System.out.println(pop.value + " 层数：" + num);
            if (num > flor) {
                flor = num;
            }
            if (pop.right != null) {
                map.put(pop.right, num + 1);
                stack.add(pop.right);
            }
            if (pop.left != null) {
                map.put(pop.left, num + 1);
                stack.add(pop.left);
            }
        }
        //所有层的元素个数已经统计出  也知道有多少层了
        int[] ints = new int[flor + 1];
        Set<Map.Entry<Point, Integer>> entries = map.entrySet();
        for (Map.Entry<Point, Integer> entry : entries) {
            ints[entry.getValue()] = ints[entry.getValue()] += 1;
        }
        int max = 0;
        for (int anInt : ints) {
            if (anInt > max) {
                max = anInt;
            }
        }

        System.out.println("最大节点数：" + max);


    }

    //求二叉树的宽度  使用队列和map
    public static void GetWidByLinkedList(Point tree) {
        LinkedList<Point> list = new LinkedList<>();
        HashMap<Point, Integer> map = new HashMap<>();
        list.add(tree);
        map.put(tree, 1);
        //当前所在行
        int curLevel = 1;
        //所在行节点数
        int curNum = 0;
        //整棵树最多节点
        int max = -1;
        while (!list.isEmpty()) {
            Point pop = list.pop();
            Integer level = map.get(pop);
            if (level == curLevel) {
                curNum++;
            } else {
                max = Math.max(max, curNum);
                curNum = 1;
                curLevel = level;
            }
            if (pop.left != null) {
                map.put(pop.left, level + 1);
                list.add(pop.left);
            }
            if (pop.right != null) {
                map.put(pop.right, level + 1);
                list.add(pop.right);
            }
        }
        System.out.println("最多节点数：" + Math.max(max, curNum));
    }

判断是否为搜索二叉树

//判断二叉树为搜索二叉树   左子节点的值 <= 当前节点的值 <= 右子节点的值
    public static void isSearchTree(Point tree) {
        //使用中序遍历
        if (tree == null) {
            return;
        }
        if (tree.left != null) {
            if (tree.left.value >= tree.value) {
                System.out.println("不是搜索二叉树");
                return;
            }
            isSearchTree(tree.left);
        }
        if (tree.right != null) {
            if (tree.value <= tree.right.value) {
                System.out.println("不是搜索二叉树");
                return;
            }
            isSearchTree(tree.right);
        }
        System.out.println("是搜索二叉树");
    }

判断是否为完整二叉树

//判断是否为完全二叉树  也就是要树是完整拥有左右子节点的 ，要么从左至右 填补叶节点
public static void isCompleteBinaryTree(Point tree) {
    //1.只要有右不左子节点 就是说明不是
    //2.满足1条件后，如果遇到只有左子节点的，则同层节点后面必须没有子节点
    //需要宽度遍历  使用队列
    LinkedList<Point> list = new LinkedList<>();
    list.add(tree);
    Point test = new Point();
    Point finPoint = test;
    while (!list.isEmpty()) {
        Point pop = list.pop();
        if (pop == finPoint) {
            if (!list.isEmpty()) {
                System.out.println("不是完全二叉树");
                return;
            }
        }
        if (pop.left == null && pop.right != null) {
            System.out.println("不是完全二叉树");
            return;
        }
        if (pop.left != null) {
            list.add(pop.left);
            if (test == finPoint && pop.right == null) {
                finPoint = pop.left;
            }
        }
        if (pop.right != null) {
            list.add(pop.right);
        }
    }
    System.out.println("是完全二叉树");
}

套路判断是否为搜索二叉树

//用二叉树套路解决是否为搜索二叉树
    public static void isSearchTreeByMethod(Point tree) {
        //左边为搜索二叉树
        //右边为搜索二叉树
        //左边值<当前值<右边值  所以我们需要知道左右两边的值  使用后序遍历
        boolean isSearch = process(tree).isSearch;
        System.out.println(isSearch?"是搜索二叉树":"不是搜索二叉树");
    }
    public static class ReturnType{
        int min;
        int max;
        boolean isSearch;
        public ReturnType(int min,int max,boolean isSearch) {
            this.min = min;
            this.max = max;
            this.isSearch = isSearch;
        }
    }
    public static ReturnType process(Point head) {
        if (head==null) {
            return null;
        }
        ReturnType LeftData = process(head.left);
        ReturnType RightData = process(head.right);
        int min = head.value;
        int max = head.value;
        if (head.left!=null) {
            //当前值  与  左节点的最小值  比较
            min = Math.min(min,LeftData.min);
            //当前值  与  左节点的最大值  比较
            max = Math.max(max, LeftData.max);
        }
        if (head.right!=null) {
            //最小值  与  右节点的最小值  比较
            min = Math.min(min,RightData.min);
            //最大值  与  右节点的最大值  比较
            max = Math.max(max,RightData.max);
        }
        boolean isSearch = true;
        if (LeftData!=null&&(!LeftData.isSearch||LeftData.max >= head.value)) {
            isSearch = false;
        }
        if (RightData!=null&&(!RightData.isSearch||RightData.min<= head.value)) {
            isSearch = false;
        }
        return new ReturnType(min,max,isSearch);
    }

套路判断是否为完全二叉树

//用套路解决是否为完全二叉树
    public static void isCBT(Point tree) {
        ReturnType process = process(tree);
        System.out.println(process.isCBT?"是完全二叉树":"不是完全二叉树");
    }
    public static class ReturnType {
        //节点高度
        int high;
        //节点个数
        int Num;
        //是否为完全二叉树
        boolean isCBT;

        public ReturnType(int high, int num, boolean isCBT) {
            this.high = high;
            Num = num;
            this.isCBT = isCBT;
        }
    }
    public static ReturnType process(Point head) {
        if (head == null) {
            return new ReturnType(0, 0, true);
        }
        ReturnType leftData = null ;
        ReturnType rightData = null ;
        int high = 1;
        int num = 1;
        boolean isCBT = false;
        if (head.left != null && head.right!=null) {
            leftData = process(head.left);
            rightData = process(head.right);
            high = leftData.high+1;
            num = leftData.Num+ rightData.Num+1;
            if (!leftData.isCBT||!rightData.isCBT) {
                return new ReturnType(high,num,false);
            }
            //层数  与  节点个数呈  N=2^L - 1
            if ((2^high-1)==num) {
                isCBT = true;
            }
        }
        return new ReturnType(high, num, isCBT);
    }

套路寻找两个节点的交汇处，也就是给出一个树，给两个点，寻找点的共同交汇处

//寻找两个节点的交会点
public static Point FindCommon (Point head,Point node1,Point node2) {
    if (head == null||head == node1||head == node2) {
        return head;
    }
    Point left = FindCommon(head.left, node1, node2);
    Point right = FindCommon(head.right, node1, node2);
    if (left!=null&&right!=null) {
        return head;
    }
    return left==null?right:left;

}

二叉树节点间的最大距离（从树上某个点到另一个点最大距离，一个点到相邻一个点的距离为1）

//二叉树节点间最大距离
    public static ReturnTypeByMaxLen maxLength(Point hear) {
        if (hear == null) {
            return new ReturnTypeByMaxLen(0,0);
        }
        ReturnTypeByMaxLen left = maxLength(hear.left);
        ReturnTypeByMaxLen right = maxLength(hear.right);
        //当前节点不参与  左节点最大距离  与  右节点最大距离比较
        int maxDistance = Math.max(left.maxConnect, right.maxConnect);
        //最大距离值与当前节点参与时  进行比较
        maxDistance = Math.max(maxDistance, left.maxDeepLen+1+ right.maxDeepLen);
        //向上一层  深度+1
        return new ReturnTypeByMaxLen(Math.max(left.maxDeepLen, right.maxDeepLen)+1,maxDistance);
    }
    public static class ReturnTypeByMaxLen {
        //最大深度
        int maxDeepLen;
        //节点最大距离
        int maxConnect;

        public ReturnTypeByMaxLen(int maxDeepLen, int maxConnect) {
            this.maxDeepLen = maxDeepLen;
            this.maxConnect = maxConnect;
        }
    }

派顿最大快乐值（多叉树）

//派顿最大快乐值（多叉树）
    public static ReturnTypeByMaxHappy MaxHappy(Employee employee) {
        if (employee.subordinates.isEmpty()) {
            return new ReturnTypeByMaxHappy(employee.happy, 0);
        }
        //如果当前节点来 返回值
        int lai = employee.happy;
        //不来
        int bu = 0;
        for (Employee subordinate : employee.subordinates) {
            ReturnTypeByMaxHappy ret = MaxHappy(subordinate);
            //如果我来  底下人不能来
            lai += ret.buMaxHappy;
            //如果我不来  底下人可以来可以不来  取最大值
            bu += Math.max(ret.laiMaxHappy, ret.buMaxHappy);
        }
        return new ReturnTypeByMaxHappy(lai,bu);
    }
    public static class ReturnTypeByMaxHappy{
        int laiMaxHappy;
        int buMaxHappy;

        public ReturnTypeByMaxHappy(int laiMaxHappy, int buMaxHappy) {
            this.laiMaxHappy = laiMaxHappy;
            this.buMaxHappy = buMaxHappy;
        }
    }

class Employee{
    int happy;  //该员工的快乐值
    List<Employee> subordinates;  //直接下级

    public Employee(int happy, List<Employee> subordinates) {
        this.happy = happy;
        this.subordinates = subordinates;
    }
}

树结构Morris遍历

我们能不能做到遍历整棵树，时间复杂度为o(n)，空间复杂度为o(1),利用原树种大量空闲指针
很多关于树结构的题，以morris为基础求出最优解。（笔试还是用正常的遍历就好，错误率低）

利用morris进行遍历树结构

//Morris先序遍历
    public static void Morris_F(tree node) {
        tree cur = node;
        tree mostRight = null;
        while (cur !=null) {
            if (cur.left != null) {
                mostRight = cur.left;
                while (mostRight.right!=null&&mostRight.right!=cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                } else {
                    //这里说明是遍历到cur第一次
                    System.out.println(cur.value);
                    mostRight.right = node;
                    cur = cur.right;
                }
            } else {
                //这里说明是最底层节点  没有左节点 在右转前输出一次
                System.out.println(cur.value);
                cur = cur.right;
            }
        }
    }
    //Morris中序遍历
    public static void Morris_M(tree node) {
        tree cur = node;
        tree mostRight = null;
        while (cur != null) {
            if (cur.left!=null) {
                 mostRight = cur.left;
                 while (mostRight.right!=null&&mostRight.right!=cur) {
                     mostRight = mostRight.right;
                 }
                 if (mostRight.right == null) {
                     mostRight.right = cur;
                     cur = cur.left;
                     continue;
                 } else {
                     mostRight.right = null;
                 }
            }
            System.out.println(cur.value);
            cur = cur.right;
        }
    }

dp套路与Morris套路什么时候使用

当我们的方法必须做第三次信息的强整合，也就是说我最后的决策必须依赖于左右两边的信息，我们使用dp套路，因为Morris每个点只返回两次。
如果不需要则就可以使用Morris。