110.平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树

思路：

1. 获取左右子树的最大高度,求相差，符合则true，不符合则false
2. 递归，只要有一个不符合，就直接输出false，终止程序

public boolean isBalanced(TreeNode root){
    if(root == null) return true;
    int temp = maxDepth(root.left) - maxDepth(root.right);
    if(temp > 1 || temp < -1) return false;
    if(!isBalanced(root.left) || !isBalanced(root.right)) return false;
    // 如果isBalanced(root.left)代码返回的是false，必定说明这个递归中有temp > 1 || temp < -1，
    // 只要有一个不满足就直接返回false
    return true;
    // 如果递归完毕，都没有返回false，那就说明每个节点的左右子树高度差都不超过1，
    // 是平衡二叉树，返回true

}

public int maxDepth(TreeNode root){
    if(root == null) return 0;
    if(root.left == null && root.right == null) return 1;
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

简化：

public int maxDepth(TreeNode root){
    if(root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

官方解答：

方法一：自顶向下的递归

时间复杂度：O(n * n)

• 平均情况：n个节点，每个节点遍历logn次
• 最坏情况：二叉树形成链表，高度为n

空间复杂度：O(n)

• 取决于递归调用的层数，不超过n层

public boolean isBalanced(TreeNode root){
    if(root == null) return true;
    return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

public int maxDepth(TreeNode root){
    if(root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

方法二：自底向上的递归

时间复杂度：O(n)

• 从底向上，每个节点只过一遍

空间复杂度：O(n)

• 取决于height递归的深度，

public boolean isBalanced(TreeNode root){
    return height(root) >= 0; 
}

public int height(TreeNode root){
    if(root == null) return 0;
    // 先递归到二叉树最下面
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    if(leftHeight == -1 || rightHeight == -1 || Math.max(leftHeight - rightHeight) > 1){
        return -1;
    } else return Math.max(leftHeight, rightHeight) + 1;
}