树形动态规划

1.套路

1.1 可能性分析

1. 如果root的左子树不是平衡二叉树，则root不是。
2. 如果root的右子树不是，则root不是。
3. 如果root的左右子树的高度差超过1，则root不是。
4. 如果以上三种没出现，那么root是平衡的。

1.2 建立数据结构

根据可能性分析列出每个结点所需信息：是否平衡、高度，建立数据结构

class ReturnType{
    public boolean isBalanced;
    public int hight;
    public ReturnType(boolean isBalanced, int hight){
        this.isBalanced = isBalanced;
        this.hight = hight;
    }
}

1.3 递归实现

递归函数处理以root为头结点的情况，得到的信息是左右子树的ReturnType（是否平衡、高度），通过他们进行上面的四个可能性分析，并返回ReturnType。

public boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }
    public ReturnType process(TreeNode root){
        //叶子节点下设置辅助null结点
        if(root == null){
            return new ReturnType(true, 0);
        }
        //递归
        ReturnType left = process(root.left);
        ReturnType right = process(root.right);

        int hight = Math.max(left.hight, right.hight) + 1;
        //左右子树都是平衡二叉树，且高度差不超过1
        boolean isBalanced = left.isBalanced && right.isBalanced 
                             &&(Math.abs(left.hight - right.hight) < 2);
        return new ReturnType(isBalanced, hight);
    }

2. 代码

同上

3. 复杂度

时间:O(n)
空间:O(n)