题解 | #判断是不是平衡二叉树#

方法一（递归+剪枝）

1.题意整理

• 给定一颗二叉树。
• 判断该二叉树是否是平衡二叉树。
• 如果一颗二叉树是空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树，则这颗二叉树是平衡二叉树。

2.思路整理

一个朴素的想法是，先利用递归计算树中每颗子树的高度，然后再根据子树高度差的绝对值不超过1、并且左右子树都必须是平衡二叉树的条件，对整颗树进行递归。

代码如下：

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //如果为空，直接返回true
        if(root==null) return true;
        //当前节点满足两个子树高度差不超过1，同时左右子树也满足
        return Math.abs(getDepth(root.left)-getDepth(root.right))<=1
               &&IsBalanced_Solution(root.left)
               &&IsBalanced_Solution(root.right);
    }
    
    //计算二叉树高度
    private int getDepth(TreeNode root){
        if(root==null) return 0;
        //左子树高度
        int l=getDepth(root.left);
        //右子树高度
        int r=getDepth(root.right);
        //算上当前节点，所以高度为两者中较大的加1
        return Math.max(l,r)+1;
    }
}

• 这种解法的缺点是需要两次递归，计算二叉树高度时，需要遍历树中所有的节点，而判断平衡时，对于每一个节点，需要递归地调用所有的父节点，如果该节点为叶子节点，则需要调用h次父节点（h为二叉树高度），所以时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$。最坏情况下，退化为链表，时间复杂度为$O(n^2)O(n^2)$。
• 一个改进的思路是，在计算高度的过程中进行剪枝，如果左右子树高度差超过1，直接返回-1。同时计算左右子树高度的时候也利用这个特点进行剪枝。从而达到每个节点只遍历一次的目的。

图解展示：

3.代码实现

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        //利用修改的计算高度的函数，正常情况下总是平衡二叉树
        return getdepth(root)!=-1;
    }
    
    //修改计算高度的函数，当不是平衡二叉树时，直接返回-1
    private int getdepth(TreeNode root){
        if(root==null)
            return 0;
        int left=getdepth(root.left);
        //如果左子树不满足，则直接返回-1
        if(left==-1){
            return -1;
        }
        int right=getdepth(root.right);
        //如果右子树不满足，则直接返回-1
        if(right==-1){
            return -1;
        }
        //不是平衡二叉树时，返回-1，否则返回对应高度
        return Math.abs(left-right)>1?-1:Math.max(left,right)+1;
    }
}

4.复杂度分析

• 时间复杂度：利用条件排除递归过程中不合法的情况，所有的节点只需遍历一次，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：最坏情况下，递归栈的深度为n，所以空间复杂度是$O(n)O(n)$。