0110：平衡二叉树

2015-04-20 约 202 字预计阅读 1 分钟次阅读

力扣第 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] 内
-10⁴ <= Node.val <= 10⁴

分析

用 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

目录

0110：平衡二叉树

题目

分析

解答