usehook - 前端码易

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

思考题：平衡二叉树判断

题目描述

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

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

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

不平衡

原题地址：leetcode 110

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

解题思路

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

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

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};

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

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}

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

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

完整代码如下

answer.ts

10class TreeNode {
20  val: number
30  left: TreeNode | null
40  right: TreeNode | null
50  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
60    this.val = (val===undefined ? 0 : val)
70    this.left = (left===undefined ? null : left)
80    this.right = (right===undefined ? null : right)
90 }
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

二叉树的最大深度

二叉树的后续遍历

专栏首页

到顶

专栏目录