题意整理

  • 输入一棵节点数为n的二叉树，判断该二叉树是否是平衡二叉树。

方法一（暴力递归）

1.解题思路

  • 首先用一个函数计算二叉树的高度。
  • 然后判断当前节点的左右子树高度差的绝对值，如果不超过1，同时递归地判断当前节点的左右子树。如果这些条件都满足，则是平衡二叉树。

2.代码实现

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;
    }
}

3.复杂度分析

  • 时间复杂度：需要遍历树中所有的节点，对于每一个节点，需要递归地调用所有的父节点，如果该节点为叶子节点，则需要调用h次父节点（h为二叉树高度），所以时间复杂度为O(nlog2n)O(nlog_2n)。最坏情况下，退化为链表，时间复杂度为O(n2)O(n^2)，所以时间复杂度为O(n2)O(n^2)。
  • 空间复杂度：最坏情况下，递归栈的深度为n，所以空间复杂度是O(n)O(n)。

方法二（剪枝）

1.解题思路

在计算高度的过程中进行剪枝，如果左右子树高度差超过1，直接返回-1。同时计算左右子树高度的时候也利用这个特点进行剪枝。从而达到每个节点只遍历一次的目的。

图解展示： alt

2.代码实现

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;
    }
}

3.复杂度分析

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