zhangdizhangdi

110. 平衡二叉树 🟩

题目

leetcode 简单

题目

给定一个二叉树，判断它是否是 平衡二叉树。
平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

题解

自底向上

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
js
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function isBalanced(root) {
  // 辅助函数：获取树的高度，如果不平衡直接返回 -1
  const getHeight = node => {
    console.log('🪵 node', node ? node.val : null)

    // 递归终止条件：空节点高度为 0
    if (node === null) return 0

    // 递归计算左子树高度，如果左子树不平衡（返回了-1），直接向上层返回 -1
    let leftHeight = getHeight(node.left)
    console.log(node.val, 'leftHeight', leftHeight)
    if (leftHeight === -1) return -1

    // 递归计算右子树高度，如果右子树不平衡（返回了-1），直接向上层返回 -1
    let rightHeight = getHeight(node.right)
    console.log(node.val, 'rightHeight', rightHeight)
    if (rightHeight === -1) return -1

    // 判断当前节点是否平衡：左右子树高度差绝对值大于 1
    if (Math.abs(leftHeight - rightHeight) > 1) {
      console.log(
        '❌',
        node.val,
        '不平衡，leftHeight',
        leftHeight,
        'rightHeight',
        rightHeight,
      )
      return -1 // 不平衡，返回标记 -1
    }

    // 如果平衡，返回当前树的高度（左右子树高度最大值 + 1）
    return Math.max(leftHeight, rightHeight) + 1
  }

  // 如果最终返回的不是 -1，说明是平衡二叉树
  return getHeight(root) !== -1
}

const tree = new TreeNode(3)
tree.left = new TreeNode(9)
tree.right = new TreeNode(20, new TreeNode(15), new TreeNode(7))
console.log('🌰', JSON.stringify(isBalanced(tree)))

console.log('------')

const tree2 = new TreeNode(1)
tree2.left = new TreeNode(
  2,
  new TreeNode(3, new TreeNode(4), new TreeNode(4)),
  new TreeNode(3),
)
tree2.right = new TreeNode(2)
console.log('🌰', JSON.stringify(isBalanced(tree2)))
执行结果
🪵 node 3
🪵 node 9
🪵 node null
9 leftHeight 0
🪵 node null
9 rightHeight 0
3 leftHeight 1
🪵 node 20
🪵 node 15
🪵 node null
15 leftHeight 0
🪵 node null
15 rightHeight 0
20 leftHeight 1
🪵 node 7
🪵 node null
7 leftHeight 0
🪵 node null
7 rightHeight 0
20 rightHeight 1
3 rightHeight 2
🌰 true
------
🪵 node 1
🪵 node 2
🪵 node 3
🪵 node 4
🪵 node null
4 leftHeight 0
🪵 node null
4 rightHeight 0
3 leftHeight 1
🪵 node 4
🪵 node null
4 leftHeight 0
🪵 node null
4 rightHeight 0
3 rightHeight 1
2 leftHeight 2
🪵 node 3
🪵 node null
3 leftHeight 0
🪵 node null
3 rightHeight 0
2 rightHeight 1
1 leftHeight 3
🪵 node 2
🪵 node null
2 leftHeight 0
🪵 node null
2 rightHeight 0
1 rightHeight 1
❌ 1 不平衡，leftHeight 3 rightHeight 1
🌰 false