题解 | #平衡二叉树#

思路：

平衡二叉树的性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
判断某二叉树是否为平衡二叉树，就需要判断任意一结点两边子树深度相差是否绝对值大于1，同时它的子树也符合平衡二叉树的规则。
则可以相当将问题不断分成子问题，使用递归。

方法一：自顶向下考察
具体做法：
写两个函数，一个递归遍历二叉树所有结点，判断该结点下的子树是否为平衡二叉树，另一个函数则递归计算该结点深度。
图中为判断函数的递归图，其中计算深度函数递归也是如此。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) //空树为平衡二叉树
            return true;
        int left = deep(root.left);
        int right = deep(root.right);
        if(left - right > 1 || left - right < -1){ //左子树深度减去右子树相差绝对值大于1
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);//同时，左右子树还必须是平衡的
    }
    public int deep(TreeNode root){//计算该子树深度
        if(root == null) //空结点深度为0
            return 0;
        int left = deep(root.left); //递归算左右子树的深度
        int right = deep(root.right);
        return (left > right) ? left + 1 : right + 1; //子树最大深度加上自己
    }
}

复杂度分析：

• 时间复杂度：，遍历二叉树需要访问所有节点，计算深度需要访问所有节点
• 空间复杂度：，递归栈最大深度为二叉树为链表时

方法二：自底向上考察
具体做法：
自底向上递归的方法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return recursion(root) != -1;//-1表示深度差大于等于2
    }
    private int recursion(TreeNode root) {
        if (root == null) 
            return 0;
        int left = recursion(root.left); //左子树深度差
        if(left == -1) 
            return -1;
        int right = recursion(root.right); //右子树深度差
        if(right == -1) 
            return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1; //-1表示深度差大于等于2
    }
}

复杂度分析：

• 时间复杂度：，遍历二叉树需要访问所有节点，每次直接累加深度，不需要额外一次遍历
• 空间复杂度：，递归栈最大深度为二叉树为链表时