What is a height-balanced binary tree?

A height-balanced binary tree is one where, for every node, the height difference between the left and right subtrees is at most one.

How do you calculate the height of a binary tree node?

The height of a node is calculated as 1 plus the maximum height of its left and right subtrees.

What happens if the tree is unbalanced?

If the difference in height between any two subtrees of a node exceeds 1, the tree is considered unbalanced, and the function should return false.

What should you do if an imbalance is found during DFS?

If an imbalance is found during DFS, you should immediately return false without continuing the traversal, as further checks are unnecessary.

How do you handle an empty tree?

An empty tree is considered balanced by definition, so the function should return true for this case.

#110

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

平衡二叉树

给定一个二叉树，判断它是否是平衡二叉树示例 1：输入： root = [3,9,20,null,null,15,7] 输出： true 示例 2：输入： root = [1,2,2,3,3,null,null,4,4] 输出： false 示例 3：输入： root = [] 输出： tr…

树深度优先搜索二叉树

题目描述

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

示例 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⁴

lightbulb

解题思路

方法一：自底向上的递归

定义函数 $height(root)$ 计算二叉树的高度，处理逻辑如下：

如果二叉树 $root$ 为空，返回 $0$ 。
否则，递归计算左右子树的高度，分别为 $l$ 和 $r$ 。如果 $l$ 或 $r$ 为 $-1$ ，或者 $l$ 和 $r$ 的差的绝对值大于 $1$ ，则返回 $-1$ ，否则返回 $max(l, r) + 1$ 。

那么，如果函数 $height(root)$ 返回的是 $-1$ ，则说明二叉树 $root$ 不是平衡二叉树，否则是平衡二叉树。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def height(root):
            if root is None:
                return 0
            l, r = height(root.left), height(root.right)
            if l == -1 or r == -1 or abs(l - r) > 1:
                return -1
            return 1 + max(l, r)

        return height(root) >= 0

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand the difference between balanced and unbalanced trees?
question_mark
Can you explain how DFS helps in both height calculation and detecting imbalances?
question_mark
Will you handle edge cases like an empty tree or a skewed tree efficiently?

warning

常见陷阱

外企场景

error
Not handling edge cases like an empty tree, which should return true.
error
Missing the early termination by not checking imbalance during traversal, leading to unnecessary work.
error
Incorrectly calculating the height of subtrees, which can cause false results in balance checking.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if the tree is a full binary tree.
arrow_right_alt
Find the diameter of the tree, which is the longest path between any two nodes.
arrow_right_alt
Determine if a binary tree is perfect, meaning all leaf nodes are at the same level and every parent has two children.

help

常见问题

外企场景

继续练习

#111 二叉树的最小深度 #112 路径总和 #113 路径总和 II