目录

0110:平衡二叉树

力扣第 110 题

题目

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

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:true

示例 2:

输入:root = [1,2,2,3,3,null,null,4,4]
输出:false

示例 3:

输入:root = []
输出:true

提示:

  • 树中的节点数在范围 [0, 5000]
  • -104 <= Node.val <= 104

相似问题:

分析

  • 用 dfs 同时返回子树深度和是否平衡,即可递归
  • 为了方便,可以用深度为 -1 代表不平衡,dfs 返回一个参数即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(u):
            if not u:
                return 0
            l,r = dfs(u.left),dfs(u.right)
            if l==-1 or r==-1 or abs(l-r)>1:
                return -1
            return max(l,r)+1
        return dfs(root)!=-1

42 ms