usehook - 前端码易

code deep_

所有专栏

免费领 30 美元额度

创建时间: 2025-04-15最后更新: 2025-12-22作者: yangbo(96862973d)

NOTE

请勿第一时间看答案, 先自己思考, 思考不出来, 再看答案

思考题：平衡二叉树判断

题目描述

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

平衡二叉树的定义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1.

例如下面三个图例, 前两个是平衡二叉树, 最后一个不是平衡二叉树.

不平衡

原题地址：leetcode 110

NOTE

目前优先使用递归的思路来解答, 如果对递归非常熟练, 也可以使用其他新的思维来解答

解题思路

前面一个题, 我们知道了如何去计算一个二叉树的最大深度, 因此, 如果我们要判断一棵树是否平衡, 只需要利用上一题的结果, 然后判断左右两个节点的深度差不超过 1 即可

我们先把上一题的答案拷贝过来

code.ts

1export function maxDepth(root: TreeNode | null): number {
2  if (root === null) {
3      return 0
4  }
5  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
6};

然后通过判断一个节点的深度差即可

code.ts

1export function isBalanced(root: TreeNode | null): boolean {
2  if (root === null) {
3    return true
4  }
5  const leftDepth = maxDepth(root.left)
6  const rightDepth = maxDepth(root.right)
7  
8  return Math.abs(leftDepth - rightDepth) <= 1
9}

不过我们还要注意一个细节, 那就是, 如果子树不平衡, 那么整棵树也是不平衡的. 因此, 我们还需要递归的去判断子树是否平衡.

code.ts

1return Math.abs(leftDepth - rightDepth) <= 1 && isBalanced(root.left) && isBalanced(root.right)

完整代码如下

answer.ts

01class TreeNode {
02  val: number
03  left: TreeNode | null
04  right: TreeNode | null
05  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
06    this.val = (val===undefined ? 0 : val)
07    this.left = (left===undefined ? null : left)
08    this.right = (right===undefined ? null : right)
09 }
10}
11
12function maxDepth(root: TreeNode | null): number {
13  if (root === null) {
14      return 0
15  }
16  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
17};
18
19export function isBalanced(root: TreeNode | null): boolean {
20  if (root === null) {
21    return true
22  }
23  const leftDepth = maxDepth(root.left)
24  const rightDepth = maxDepth(root.right)
25  
26  return Math.abs(leftDepth - rightDepth) <= 1 && isBalanced(root.left) && isBalanced(root.right)
27}
28

专栏首页

到顶

专栏目录