Tech Interview Handbook：树（Tree）编码面试专题——遍历、BST 性质与递归技巧全解

本文基于 Tree 专题文档 展开，系统讲解二叉树与二叉搜索树（BST）的核心术语、三种遍历方式的递归与迭代写法、BST 的复杂度特性，以及面试中必须熟练掌握的递归技巧、分层遍历与常见边角用例。仓库内还附带了 Python / JavaScript 的遍历与树操作参考实现，可直接对照学习，读完你可以独立完成任意树形题目的递归/迭代双写。

一、什么是树，以及面试中要重点掌握什么

树（Tree）是一种广泛使用的抽象数据类型，用一组相连的节点表示层级结构：树中每个节点可以连接多个子节点，但只能连接恰好一个父节点，唯一例外是没有父节点的根节点。树是一棵无向、连通且无环的图——不存在环或回路；每个节点都可以视为自己子树的根节点，这正让 递归 成为遍历树的核心技巧。

从面试角度看，题目几乎都围绕二叉树（binary tree）出题，而不是三叉树（3 个儿子）或 N 叉树（N 个儿子）。因此本专题聚焦二叉树及其特例——二叉搜索树（BST）。树也常用来表示层级数据，例如文件系统、JSON、HTML 文档。若有余力，可进一步查看仓库中的 Trie 专题，Trie 是一种用于高效存储与检索字符串的进阶树结构。

二、必须掌握的基本术语

术语准确性直接决定你与面试官沟通的效率。以下是文档给出的核心术语表：

术语	定义
Neighbor（邻居）	某节点的父节点或子节点
Ancestor（祖先）	沿父节点链可达的节点
Descendant（后代）	位于某节点子树内的节点
Degree（度）	节点的子节点数量
Degree of a tree（树的度）	树中所有节点度的最大值
Distance（距离）	两节点间最短路径上的边数
Level/Depth（层/深度）	节点到根节点的唯一路径上的边数
Width（宽度）	某一层的节点数

二叉树的两个关键结构定义

• 完全二叉树（Complete binary tree）：除了最后一层外，每一层都被完全填满，且最后一层的节点都尽量靠左。
• 平衡二叉树（Balanced binary tree）：每个节点的左右子树高度差不超过 1。

这两个定义在判断"树是否平衡"（如 LeetCode 的 Balanced Binary Tree 类题目）时是直接的判定依据。

三、三种遍历方式：递归是默认选择，迭代是加分项

对于文档中给出的经典示例树（根为 1，含节点 2、5、6、7、9、11 等），三种遍历的结果分别是：

• 中序遍历（In-order traversal）：左 -> 根 -> 右
  • 结果：2, 7, 5, 6, 11, 1, 9, 5, 9
• 前序遍历（Pre-order traversal）：根 -> 左 -> 右
  • 结果：1, 7, 2, 6, 5, 11, 9, 9, 5
• 后序遍历（Post-order traversal）：左 -> 右 -> 根
  • 结果：2, 5, 11, 6, 7, 5, 9, 9, 1

一个容易被考到的细节：仅凭中序遍历的结果不足以唯一序列化一棵树，还必须配合前序或后序遍历。这也是 LeetCode "Construct Binary Tree from Preorder and Inorder Traversal" 一题的理论前提。

递归写法：先写对，再考虑边界

三种遍历的递归实现都遵循同一模式：处理当前节点 + 递归处理左右子树，且递归函数必须显式检查 node 为 null 的基线情况。二叉树题的解法大多是这个模式的变体。

迭代写法：面试中的"第二道考题"

文档特别提醒：要非常熟悉递归地写前序、中序、后序遍历，并把写出迭代版本作为进阶自测。面试官经常会在候选人很快写完递归版后，追问迭代版本。仓库的 实验工具目录 中给出了三种遍历的迭代参考实现，核心思想是用显式栈模拟递归调用栈。以下摘录其中的前序遍历（非侵入式，不修改节点）：

def preorder_traversal(root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    if not root:
        return []
    result = []
    stack = [root]
    while len(stack) > 0:
        curr_node = stack.pop()
        result.append(curr_node.val)
        if curr_node.right:
            stack.append(curr_node.right)
        if curr_node.left:
            stack.append(curr_node.left)
    return result

注意入栈顺序：先压右孩子，再压左孩子，这样弹栈时先处理左孩子，符合"根 -> 左 -> 右"的顺序。同一文件中的中序与后序迭代实现采用了"压入节点后将其对应子指针置 None 作为已访问标记"的技巧（如 curr_node.left = None），属于侵入式写法，在面试中可以先讲思路再说明该标记技巧。JavaScript 版本的等价递归实现见 treeEqual.js 与 treeMirror.js 同目录。

四、二叉搜索树（BST）：性质、复杂度与验证

BST 最重要的性质：中序遍历一棵 BST，得到的就是全部元素的有序序列。这一性质是"验证二叉树是否为 BST"（Validate Binary Search Tree）类题目的标准解法基础——中序序列必须严格递增。文档特别强调：要对 BST 的性质非常熟悉，尤其是验证一棵二叉树是否为 BST，这道题出现的频率比多数人预期的更高。另外，当题目涉及 BST 时，面试官通常期望你给出优于 O(n) 的解法，即利用有序性做剪枝或二分式查找。

BST 的时间复杂度

操作	大 O
Access（访问）	O(log n)
Search（查找）	O(log n)
Insert（插入）	O(log n)
Remove（删除）	O(log n)

上表是平衡 BST 的最优情况。空间复杂度方面：遍历一棵平衡树需要 O(h)（h 为树高），而遍历极度倾斜的树（退化成链表形态）则为 O(n)。这也解释了为什么 BST 题的边界用例总包含"斜树"。

五、面试注意事项与边角用例

面试中的表现要点

• 递归版三种遍历必须默写级熟练；
• 准备好迭代版本的现场推导（用栈模拟）；
• 涉及 BST 时主动说明"可以利用有序性，把 O(n) 优化到 O(log n)"。

必须覆盖的边角用例（Corner cases）

1. 空树；
2. 单节点树；
3. 两节点树；
4. 极斜的树（形如链表）。

这四个用例覆盖了 null 判断、递归深度上界、以及空间复杂度退化到 O(n) 的全部场景，写代码时先声明这些情况的处理方式，是面试沟通的加分项。

六、常见基础操作（Common routines）

许多树题的解法都是下面这些基础操作的一个或多个组合。文档列出的清单是：

• 插入值（Insert value）
• 删除值（Delete value）
• 统计树的节点数（Count number of nodes in tree）
• 判断某个值是否在树中（Whether a value is in the tree）
• 计算树高（Calculate height of the tree）
• 二叉搜索树专项：
  • 判断是否为 BST（Determine if it is a binary search tree）
  • 获取最大值（Get maximum value）
  • 获取最小值（Get minimum value）

BST 中"最大值/最小值"正是利用有序性的典型应用：一直走到最右（最左）即可，O(h)。

仓库的实验目录还附带了两个高频"树形递归"参考实现，恰好对应练习清单中的 Same Tree 与 Invert Binary Tree，可以直接作为递归模板。以 tree_equal.py 为例：

def tree_equal(node1, node2):
    if not node1 and not node2:
        return True
    if not node1 or not node2:
        return False
    return node1.val == node2.val and \
        tree_equal(node1.left, node2.left) and \
        tree_equal(node1.right, node2.right)

它体现了树题递归的两个通用模式：同时为空才算相等（双重基线），以及逐层同步递归左右子树。镜像翻转 tree_mirror.py 则是"先交换当前节点的左右子指针，再递归两棵子树"：

def tree_mirror(node):
    if not node:
        return
    node.left, node.right = node.right, node.left
    tree_mirror(node.left)
    tree_mirror(node.right)

对应的 JavaScript 实现分别见 treeEqual.js 与 treeMirror.js，逻辑与 Python 版一一对应。

七、三种核心解题技巧

1. 用递归

递归是遍历树的默认方法。当你发现"子树问题的解可以组装出整棵树的解"时，就该上递归。使用递归时务必检查基线情况，通常就是节点为 null。另外，有时递归函数需要返回两个值——例如求最大路径和时，一个返回值是"以该节点为端点的最长单边路径和"，另一个是"经过该节点的最优答案"，这是进阶考点。

2. 按层遍历（Level-order）

题目要求按层处理节点时，使用广度优先搜索（BFS），即队列逐层出队、每轮处理完当前层全部节点的标准模式。

3. 节点求和（Summation of nodes）

当题目涉及"沿途节点求和"时，先确认节点值是否可能为负数——这决定了能否用"遇到非正数就剪枝"之类的贪心假设。

八、刷题路线：必做题 + 推荐练习

必做题（Essential questions）

这些是学习本专题时必须动手练习的题目：

• 二叉树：
  • Maximum Depth of Binary Tree（二叉树的最大深度）
  • Invert/Flip Binary Tree（翻转二叉树）
• 二叉搜索树：
  • Lowest Common Ancestor of a Binary Search Tree（BST 的最近公共祖先）

前两题在仓库中恰好有对应参考实现（见 tree_mirror.js 与前述递归模板），最大深度则是递归返回值的直接应用：1 + max(height(left), height(right))。BST 的 LCA 则是利用有序性剪枝：两目标值同时落在左子树、或同时落在右子树时才递归，否则当前节点即为答案，均优于 O(n) 全遍历。

推荐练习题（Recommended practice questions）

学完专题、完成必做题之后，按下面清单继续刷：

• 二叉树：
  • Same Tree（两棵树是否相同）
  • Binary Tree Maximum Path Sum（二叉树最大路径和）
  • Binary Tree Level Order Traversal（按层遍历）
  • Lowest Common Ancestor of a Binary Tree（二叉树的最近公共祖先）
  • Binary Tree Right Side View（树的右视图）
  • Subtree of Another Tree（另一棵树的子树）
  • Construct Binary Tree from Preorder and Inorder Traversal（由前序与中序构造二叉树）
  • Serialize and Deserialize Binary Tree（二叉树的序列化与反序列化）
• 二叉搜索树：
  • Validate Binary Search Tree（验证 BST）
  • Kth Smallest Element in a BST（BST 中第 K 小的元素）

从选题分布可以看出本专题的能力模型：递归双值返回（最大路径和）、BFS 分层（层序、右视图）、序列与树的相互转换（构造、序列化，呼应"中序不足以唯一确定树"的结论）、以及 BST 有序性应用（验证、第 K 小）。

九、学习资源

文档推荐的学习资源分为三层，可按时间预算裁剪：

• 视频（核心）：
  • UC San Diego（Coursera 数据结构课程）的 Trees 章节；
  • 剑桥大学 Samuel Albanie 的系列短视频：A Brief Guide to Binary Search Trees、A Brief Guide to Red-Black Trees、A Brief Guide to B-trees（原帖均附有课程 slides）。
• 阅读（核心）：basecs 的两篇入门文章——How To Not Be Stumped By Trees 与 Leaf It Up To Binary Trees。
• 进阶（时间富余时）：basecs 的 The Little AVL Tree That Could、Busying Oneself With B-Trees、Painting Nodes Black With Red-Black Trees。

红黑树、AVL、B 树属于数据结构底层知识，面试中一般只需理解"它们通过旋转/多路分支维持平衡、从而把 BST 操作稳定在 O(log n)"，无需手写实现。

仓库另外在 AlgorithmCourses.md 中汇总了通用的算法课程推荐（如 AlgoMonster、Grokking the Coding Interview 等按"模式"组织的刷题课程），可作为树专题之外的整体复习资源参考。

十、小结

树专题的面试考察高度收敛：术语与结构定义（完全/平衡二叉树）、三种遍历的递归与迭代双写、BST 有序性的 O(log n) 应用与验证、四个边角用例、以及"递归双返回值 + BFS 分层 + 求和判负"三件套。按本文的路线走一遍——先精读 Tree 专题文档 的术语与技巧，再对照 实验目录中的 Python/JS 参考实现 手写每个基础 routine，最后按必做题、推荐题的顺序完成刷题，即可覆盖面试中绝大多数树形题目。