手帐 Blog

主题

17 · 二叉树递归经典 ​

目标：会做最大深度、对称、路径总和、直径；每题能说清「递归返回什么」。

为什么面试会考 ​

这些题不考花哨数据结构，考子问题拆分：

  • 深度 = 1 + max(左深, 右深)
  • 对称 = 左右镜像比较
  • 路径和 = 沿路径减数，到叶判断
  • 直径 = 经过某结点的「左深 + 右深」取全局最大

会拆，后面 LCA、序列化都顺。

零基础概念：递归返回值 ​

题函数返回 / 副作用
104 深度返回数字
101 对称返回布尔
112 路径和返回布尔
543 直径返回深度，同时用外部变量记直径

JS 模板：后序汇总信息 ​

js
function dfs(node) {
  if (!node) return 0 // 空树深度 0
  const L = dfs(node.left)
  const R = dfs(node.right)
  // 用 L、R 更新答案
  return Math.max(L, R) + 1
}

精讲题 ​

LeetCode 104. 二叉树的最大深度 ​

js
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) return 0
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

LeetCode 101. 对称二叉树 ​

比较两棵子树是否镜像：

js
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  const mirror = (a, b) => {
    if (!a && !b) return true
    if (!a || !b) return false
    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left)
  }
  return mirror(root.left, root.right)
}

LeetCode 112. 路径总和 ​

从根到叶，路径和是否等于 targetSum。

js
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function (root, targetSum) {
  if (!root) return false
  if (!root.left && !root.right) return root.val === targetSum
  const next = targetSum - root.val
  return hasPathSum(root.left, next) || hasPathSum(root.right, next)
}

LeetCode 543. 二叉树的直径 ​

直径 = 任意两结点最长路径的边数。对每个结点，左深 + 右深 可能是答案。

js
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  let best = 0
  const depth = (node) => {
    if (!node) return 0
    const L = depth(node.left)
    const R = depth(node.right)
    best = Math.max(best, L + R)
    return Math.max(L, R) + 1
  }
  depth(root)
  return best
}

练习清单 ​

题提示
LeetCode 111. 二叉树的最小深度注意单侧为空时不能当 0
LeetCode 226. 翻转二叉树交换左右再递归
LeetCode 110. 平衡二叉树深度差 ≤ 1；可后序返回高度或 -1
LeetCode 437. 路径总和 III（可选）前缀和 + DFS

今日验收 ​

  • [ ] 104 / 101 / 112 能默写
  • [ ] 543 能解释「返回深度、副作用记直径」
  • [ ] 空结点、单结点边界都想过

若你以前见过 ​

「后序先算左右子树再合并」和 DP 的「先算子状态」是同一感觉。