树形dp套路

image.png
向左边要信息，右边要信息，得到全集，加工出头节点的信息
是否所有树题目都能用套路解？
不一定，看问题能否分解成向左右两树要信息。
比如找整棵树数值的中位数，还是看题。

题目6: 常用二叉树结构的种类
image.png
问题一： 搜索二叉树
image.png
解法1: 套路解，左右子树拿信息
左程云解法
image.png
左程云另一个写法
image.png
我的：

  2.     /**搜索二叉树
  3.      * 注意首先要判断是不是完全二叉树*/
  4.     public static Info process2(Node head){
  5.         if(head == null ) return null;
  6.         Info left = process2(head.left);
  7.         Info right = process2(head.right);
  8.         boolean isBst = true;
  9.         int max = head.value;
  10.         int min = head.value;
  11.         if(left!=null){
  12.             isBst = isBst &&  left.isBST && left.max< head.value;
  13.             max = Math.max(left.max, max);
  14.             min = Math.min(left.min, max);
  15.         }
  16.         if(left!=null){
  17.             isBst = isBst && right.isBST && right.min > head.value;
  18.             max = Math.max(right.max, max);
  19.             min = Math.min(right.min, min);
  20.         }
  21.         return new Info(isBst, max, min);
  22.     }

tips；static int生成的变量称为动态检查，
递归程序中，如果跟要求的信息不一样，就生成一个外部静态节点。
解法2： 中序遍历看是否是升序
image.png
问题二： 完全二叉树，就是碰到空叶子节点以后，后面不能再有节点。
step1 ： 宽度优先遍历，如果任何一个节点，有有孩子但是没有左孩子，那么就不是完全二叉树
step2: 如果遇到了第一个左右孩子不双全的情况下，剩下的一定全是叶子节点
image.png
代码（我的）： 第十一行有错误
image.png

 public static boolean process(Node head){
        if(head== null) return true;
        /**宽度优先遍历的应用*/
        Queue<Node > queue = new LinkedList<>();
        queue.add(head);
        Node cur ;
        Boolean both = true;
        while(!queue.isEmpty()){
            cur = queue.poll();
            if(both == false){
                return head.left == null && head.right == null;
            }
            if(head.left== null && head.right!=null) return false;
            if(head.left!=null){
                queue.add(head.left);
            }
            if(head.right !=null ){
                queue.add(head.right);
            }
            if(head.left ==null  || head.right == null){
                both = false;
            }
        }
        return true;

    }

左程云版本：
image.png
tips ： 注释
image.png

题目三： 判断满二叉树
解法1 ： 求节点个数和 最大深度的关系，其实只要选右节点就行 2 ^ L -1;
解法2: 看左右高度是否相等，看左右节点个数是否满足： 节点个数 = 高度的L次方-1
image.png
我的：
每一个节点左右两树高度都相等

  /**是不是满二叉树*/
    public static Info3 process3(Node head){
        if(head == null )return new Info3(true,0);
        Info3 left = process3(head.left);
        Info3 right = process3(head.right);
        int height = Math.max(left.height , right.height ) +1;
        boolean isFull = left.isFull && right.isFull && left.height == right.height;
        return new Info3(isFull, height);
    }

题目四： 判断平衡二叉树
tips： 平衡二叉树，满二叉树，搜索二叉树， 都可以用套路解
平衡二叉树，左树高度 右树高度 ，高度差不能超过1
image.png
image.png