树的 DFS 与 BFS

二叉树面试全景

树题占算法面试很大比重。核心能力：四种遍历（前中后层）、递归定义子问题、全局变量/返回值传递信息。

空树：if not root: return ... 几乎每题必备。

DFS 递归模板

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

路径和 / 直径 / 最近公共祖先：在递归中向上返回高度、距离或布尔标记。

验证 BST：传递 (lo, hi) 区间约束，不仅比较父子。

迭代 DFS

用栈存 (node, state) 模拟后序；或 Morris 遍历 O(1) 空间（了解即可）。

前序迭代：

def preorder(root):
    if not root:
        return []
    stack, out = [root], []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out

右子先入栈保证左先出。

BFS 层序

见 week02-stack-queue 队列模板。变体：锯齿形（层数奇偶 reverse）、右视图（每层最后一个）、Connect 同级指针。

经典题型

| 类型 | 思路 | |------|------| | 对称树 | 双递归比较 mirror | | 翻转 | 交换左右子递归 | | 构造树 | 前+中 / 后+中 找根划分 | | LCA | 递归：根等于 p/q 或左右各找到则当前为 LCA |

从前序与中序构造：

def build_tree(preorder, inorder):
    if not preorder:
        return None
    root_val = preorder[0]
    mid = inorder.index(root_val)
    root = TreeNode(root_val)
    root.left = build_tree(preorder[1:1+mid], inorder[:mid])
    root.right = build_tree(preorder[1+mid:], inorder[mid+1:])
    return root

生产环境用哈希存 inorder 下标 O(n)。

DFS vs BFS 选型

• 深度/路径/回溯：DFS。
• 最短层数/扩散：BFS。
• 节点数极大、树很深：DFS 注意栈溢出，迭代或 BFS。

N 叉树同样适用；图遍历需 visited 防环。

与后续章节

图 DFS/BFS 见 week03-backtracking-graph。站内 /chapters/algorithm-lab/problems 有树相关 Lab。

实战巩固与面试表达

本篇属于 8 周冲刺 week02-tree-dfs-bfs 主题。复习时先闭卷回答 frontmatter 中三张 flashcard，再展开口述两个「为什么」：为什么这种方案能 work、边界失败时如何降级。与相邻章节对照：算法篇强调复杂度与模板，Go 篇强调工程默认写法，中间件篇强调线上故障案例。

动手与自检清单

用 25 分钟限时做 1 道相关练习题或画出一张架构/数据结构示意图；用 5 分钟写 STAR 片段说明你在项目里是否用过类似技术。记录 3 个面试追问及你的标准答法，存入 /zh/notebook/master-plan 笔记。若某点不熟，回到对应 /chapters 交互 Lab 重新走一遍流程，比死记卡片更有效。

易错点提醒

避免只背名词不会画图；避免只说优点不谈 trade-off（性能、一致性、运维成本至少提一项）；避免把学习 Demo 说成百万 QPS 生产。回答时使用「场景 → 方案 → 结果 → 反思」四段式，体现工程成熟度。

自检

手写：最大深度、翻转、层序、LCA（二叉树版）。能口述中序 BST 有序性的证明。