描述

题目描述

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树

平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

注:我们约定空树是平衡二叉树。

示例

输入:{1,2,3,4,5,6,7}
返回值:true
引言

有关树的题目很多都可以使用递归解决,但需要注意栈溢出的问题。

递归只要关心递归方法能实现的功能,而无需陷入其中去理解每一层递归的细节,否则只会自行提高题目难度

知识点:二叉树,递归
难度:二星


题解

解题思路

一看到树的题目就要想到使用递归解决问题,而且有时候可以通过使用递归、遍历等框架解题。

本题可以使用自顶向下的暴力法来遍历整棵树,时间复杂度相对较高

也可以使用自底向上的递归,最关键就是要阻断递归,递归到一定情况要结束当前节点递归,降低时间复杂度

方法一:暴力法:自顶向下

算法流程:
  • 通过比较每个节点的左右子树的最大高度差, 来判断此子树是否是二叉平衡树。
  • 若树的所有子树都平衡时,该树才是平衡二叉树。
Java 版本代码如下:
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;
        // 高度差不能大于1,并且左右子树也是同样高度差要小于等于1
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;  
        } 
         // 左右子树中高度较大的作为当前节点高度
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}
Python 版本代码如下:
class Solution:
    def IsBalanced_Solution(self, root: TreeNode) -> bool:
        if not root: return True
        # 高度差不能大于1,并且左右子树也是同样高度差要小于等于1
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
            self.IsBalanced_Solution(root.left) and self.IsBalanced_Solution(root.right)

    def depth(self, root):
        if not root: return 0
        # 左右子树中高度较大的作为当前节点高度
        return max(self.depth(root.left), self.depth(root.right)) + 1

复杂度分析:

时间复杂度 O(Nlog2N):最差情况下,需要遍历树所有节点判断是否平衡,需要O(N)。判断每个节点最大高度需要递归左右子树,需要占用 O(log2N),所以总共占用O(Nlog2N)
空间复杂度O(N):最差情况下(树退化为链表时),递归需要使用O(N) 的栈空间。

方法二:自底向上递归

图解

image-20210622182344258

算法流程:
  • 判断空树,题目要求空树也是平衡二叉树

  • 递归计算当前root左右子树的高度差

  • 注意:递归过程中有左/右子树不平衡,则该树不平衡,相当于可行性剪枝,没必要遍历所有节点

  • 递归到底后,自底向顶,每次+1,不断计算高度,直到递归到某个节点使得左右子树高度差大于1,则返回-1表示不平衡

  • 左右子树中高度较高的, 作为当前节点的高度, 用于向上递归判断是否平衡

  • 递归终止条件:

    • root 为 null
    • 左右子树高度差大于1,即左右子树其中一个节点返回-1,则递归终止,阻断递归,表示不是平衡二叉树
  • 递归方法的功能:获取当前节点的树的高度

Java 版本代码如下:
public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        // 空树也是平衡二叉树
        if(root == null) {
            return true;
        }
        return getHeight(root) != -1;
    }

    public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        // 递归计算当前root左右子树的高度差
        int left = getHeight(root.left);
        // 当前节点左子树不平衡,则该树不平衡,相当于可行性剪枝,没必要遍历所有节点
        if(left < 0) {
            return -1;
        } 
        int right = getHeight(root.right);
        if(right < 0) {
            return -1;
        } 
        // 自底向顶,每次+1,不断计算高度,直到递归到某个节点使得左右子树高度差大于1,则返回-1表示不平衡
        // 左右子树中高度较高的, 作为当前节点的高度, 用于向上递归判断是否平衡
        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}
Python 版本代码如下:
class Solution:
    # 计算root节点的高度
    def high(self,root):
        if root == None:
            return 0
        left = self.high(root.left)
        right = self.high(root.right)
        ans = max(left,right)+1
        return ans

    def IsBalanced_Solution(self, pRoot):
        if pRoot == None:
            return True
        # 提前阻断,可行性剪枝
        if not self.IsBalanced_Solution(pRoot.left):
            return False
        if not self.IsBalanced_Solution(pRoot.right):
            return False
        highleft = self.high(pRoot.left)
        highright = self.high(pRoot.right)
        isbalance = highleft - highright
        # 当前节点高度差
        if isbalance > 1 or isbalance < -1:
            return False
        return True
        # write code here
复杂度分析:

时间复杂度O(N):递归最差情况下(树退化为链表时),需要使用 O(N) 的栈空间。
空间复杂度O(N):递归需要使用额外的树节点数量的堆栈空间

总结:解决树的问题时,不仅需要处理特殊情况,还需要注意栈溢出,以及不要陷入递归的逻辑当中