110. 平衡二叉树

平衡二叉树 #

题目 #

给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:

一个二叉树每个节点   的左右两个子树的高度差的绝对值不超过 1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]
3

/
9 20 /
15 7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]
   1
  / \
 2   2
/ \

3 3 /
4 4 返回 false 。

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:
3

/
9 20 /
15 7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:
   1
  / \
 2   2
/ \

3 3 /
4 4

Return false.


分析 #


题解 #











class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.height(root) >= 0

    def height(self, root: TreeNode) -> int:
        if root is None:
            return 0
        lh = self.height(root.left)
        rh = self.height(root.right)
        if lh >= 0 and rh >=0 and abs(lh - rh) <= 1:
            return max(lh, rh) + 1

        return -1






本文访问量

本站总访问量

本站总访客数