题解 | #平衡二叉树#

39、平衡二叉树

解题思路：

这道题目其实跟二叉树的深度这道题用到的方法是一样的，为什么说是一样的呢？因为我们求二叉树的深度，其实就是求了左右子树的深度的最大值，但是这道题目是要让我们判断二叉树是不是平衡树。

我们都知道如何判断一棵二叉树是不是平衡二叉树，就是它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

所以，这个时候我们只需要判断左右子树的深度之差有没有超过1，若超过了则不是平衡的，反之则为平衡二叉树。

我们先来回顾一下求二叉树深度的代码：

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

我们只需要在上面的代码加上判断左右子树的深度之差即可。

(左子树深度-右子树深度) > 1，不是平衡树

所以代码可以改为：

    boolean isBalanced = true; // 默认标记为true
    public boolean IsBalanced_Solution(TreeNode root) {
        TreeDepth(root);
        return isBalanced;
    }

public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0; // 递归终止
        int l = TreeDepth(root.left);
        int r = TreeDepth(root.right);

        if(Math.abs(l-r) > 1){
            isBalanced = false;  // 不是平衡树
        }

        return Math.max(l,r)+1; // 求深度
    }

但是，上面的代码总是遍历完全部的节点，我们想想，如果一判断到左右子树的深度之差大于1，即这个二叉树就不可能再是平衡树了。

所以，我们还可以对上面代码进行优化。

进行剪枝：当判断到左右子树的深度之差大于1的时候，则返回-1。每次递归结束判断返回值是否-1，若为-1，则立即返回。

所以优化后的代码为：

    boolean isBalanced = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        TreeDepth(root);
        return isBalanced;
    }

public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        int l = TreeDepth(root.left);
        if(l == -1)  return -1;  // 提前返回
        int r = TreeDepth(root.right);
        if(r == -1)  return -1;  // 提前返回
         if(Math.abs(l-r) > 1){
            isBalanced = false;  // 不是平衡树
            return -1;  // 加一个标记-1，已经不可能是平衡树了
        }

        return Math.max(l,r)+1;
    }

看一下整体动态图：

复杂度分析：

时间复杂度：O(N)。N为树的节点个数。最差情况下需要遍历所有节点。

空间复杂度：O(N)。若树退化成了链表，则递归深度为节点的个数，需要用到O(N)的栈空间。