树 · 遍历入门

1. 核心原理

二叉树（binary tree）是每个节点最多有两个孩子的有根树。遍历指按某种确定的顺序依次访问每个节点恰好一次。本章覆盖四种基本遍历——前序、中序、后序、层序——以及它们的递归和迭代实现。所有遍历时间都是 O(n)，区别在空间复杂度和访问根的时机。

四种遍历的定义

记 L = 递归遍历左子树，R = 递归遍历右子树，V = 访问当前节点。三种 DFS 遍历的差别只在 V 的位置：

前 / 中 / 后都是 DFS，深度优先；层序是 BFS，广度优先。

递归 DFS

递归版直接对应定义。前序遍历的三行：

def preorder(node):
    if node is None: return
    visit(node)            # V
    preorder(node.left)    # L
    preorder(node.right)   # R

把 visit(node) 放在两次 preorder 之间得中序，放在最后得后序。时间 O(n)，空间 O(h) 用于递归栈，h 为树高，最坏 O(n)（链式树）。

迭代 DFS：把系统调用栈显式化

递归调用时编译器/解释器维护一个"系统调用栈"保存局部变量和返回地址。迭代版把这个隐式栈替换成一个数据结构层面的显式栈。

• 前序迭代最简：弹栈→访问→压右孩子→压左孩子。压"右后左"是因为栈 LIFO，下次先弹左孩子。
• 中序迭代用 push-all-left：从根开始一路 cur = cur.left 压栈，直到 cur == None；然后弹栈访问，再令 cur = cur.right，继续循环。
• 后序迭代有两种思路：（a）按"根-右-左"前序跑一遍再反转得到"左-右-根"；（b）双栈或"上次访问的孩子"标记，详见 §4.

迭代版好处：不受语言默认栈深限制（Python 默认 1000），控制流明确，内存占用可控。

层序 BFS

用队列保存"待访问的节点"，每次从队首弹出访问、把孩子压到队尾。要"按层分组输出"，在每轮 while 开始时用 len(q) 锁定当前层的节点数：

while q:
    size = len(q)
    for _ in range(size):
        node = q.popleft()
        ...                   # 把 node.left / node.right 加入队列

时间 O(n)，空间 O(w)，w 是树的最大宽度——完全二叉树最坏 n/2。

Morris 遍历：O(1) 额外空间

当面试官追问"能不能用 O(1) 额外空间做中序遍历"，答案是 Morris 遍历。核心思想：进入节点 cur 时，找到它左子树的最右节点（中序前驱），把这个前驱的 right 指针临时指向 cur——左子树遍历完后能"沿这条假边"回到 cur。下次再回到前驱时发现 right 已经指向 cur，就把假边断开、访问 cur、转向右子树。

每条边至多被遍历常数次，时间仍 O(n)，空间 O(1)。代价是临时改了树结构，并发或只读输入下不能用。

时间空间汇总

2. 通用模板

下面给前序迭代 + BFS 层序两种基础模板。中序、后序见 §4 例题。Python / Java / C++ 三套实现行为一致，区别只在底层栈 / 队列容器选择。

# 写法一：前序迭代（用显式栈）
class Solution:
    def preorderTraversal(self, root):
        if root is None:
            return []
        result = []
        stack = [root]                             # 显式栈
        while stack:
            node = stack.pop()                     # 弹栈
            result.append(node.val)                # 访问根
            if node.right:
                stack.append(node.right)           # 右先入栈
            if node.left:
                stack.append(node.left)            # 左后入栈，下次先弹
        return result


# 写法二：BFS 层序（用队列）
from collections import deque

class Solution:
    def levelOrder(self, root):
        if root is None:
            return []
        result = []
        q = deque([root])
        while q:
            level = []
            for _ in range(len(q)):                # 当前层节点数固定
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(level)
        return result

// 前序迭代
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
        return result;
    }
}

// BFS 层序
class Solution2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

// 前序迭代
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == nullptr) return result;
        stack<TreeNode*> stk;
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            result.push_back(node->val);
            if (node->right) stk.push(node->right);   // 右先入栈
            if (node->left) stk.push(node->left);     // 左后入栈，下次先弹
        }
        return result;
    }
};

// BFS 层序
class Solution2 {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();                      // 当前层节点数固定
            vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};

时间 O(n)、空间 O(h) 或 O(w)。

几点要说明：

• BFS 锁定层节点数：每轮 while 开始时用 for _ in range(len(q)) 锁定当前层节点数。如果不锁定，内层循环把后入队的下一层节点也算进当前层，导致层级错位。
• Python 队列必须用 deque：list.pop(0) 是 O(n)（要左移所有元素），BFS 整体退化到 O(n²)。deque.popleft() 是 O(1)。
• Java 用 ArrayDeque 当栈也当队列：不要用 java.util.Stack（继承自 Vector，所有方法同步，慢）。ArrayDeque 的 push / pop / offer / poll 都是 O(1)。
• C++ 栈队列分别用 stack / queue：stack<TreeNode*> 默认底层是 deque，queue<TreeNode*> 同理。两者接口 push / pop / top（栈）/ front（队列）都是 O(1)。
• 空树判断要在迭代版手动写：递归版的递归出口自动处理 nullptr；迭代版若没写 if root == nullptr return 会把 nullptr 压栈后弹出来访问 ->val，直接段错误 / NPE。

彩色标记法：前/中/后三序统一模板

上面前序迭代和后面 §4.1 中序、§6.1 后序看起来是三套割裂的代码——其实可以抽出一个统一骨架，用栈帧带一个 visited 标记表示"是不是回头访问"。模板就一份，前/中/后只是子节点和"自己"的入栈顺序不同：

def traverse(root, order):
    """order ∈ {'pre', 'in', 'post'}"""
    if root is None:
        return []
    result, stack = [], [(root, False)]
    while stack:
        node, visited = stack.pop()
        if visited:
            result.append(node.val)            # 回头时才输出
            continue
        # 第一次访问 node — 按目标序的反向重新入栈
        if order == 'pre':
            # 输出顺序 根→左→右 → 入栈反向：右、左、根(visited=True)
            if node.right: stack.append((node.right, False))
            if node.left:  stack.append((node.left, False))
            stack.append((node, True))
        elif order == 'in':
            # 输出顺序 左→根→右 → 入栈反向：右、根(visited=True)、左
            if node.right: stack.append((node.right, False))
            stack.append((node, True))
            if node.left:  stack.append((node.left, False))
        elif order == 'post':
            # 输出顺序 左→右→根 → 入栈反向：根(visited=True)、右、左
            stack.append((node, True))
            if node.right: stack.append((node.right, False))
            if node.left:  stack.append((node.left, False))
    return result

每个节点在栈里出现两次：第一次 visited=False 是"展开",把自己和孩子重新按目标序的反向入栈；第二次 visited=True 才真正输出值。一份代码三种序，区别只在三行 append 顺序。

时间 O(n)，空间 O(h)——栈里同时存在的"visited=False 待展开"帧最多是当前路径上的节点数，加上路径上每个祖先的"visited=True"帧（每个祖先 ≤ 2 帧），所以严格上界是 2h 帧 = O(h)。比上面那份前序专用模板多一个常数 2，但换来"一套代码"的好处。

这种"二次入栈 + visited 标记"思路在 LC 314（垂直序）/ LC 987（带列编号的垂直序）等需要"先展开后处理"的题里也能直接照搬。

3. 母题精讲

LeetCode 144. Binary Tree Preorder Traversal

链接：LeetCode 144

题目（中文翻译）：给一个二叉树的根节点 root，返回它节点值的前序遍历——按"根 → 左 → 右"的顺序访问每个节点。

数据范围：

• 节点数：0 ≤ n ≤ 100
• 节点值：-100 ≤ val ≤ 100

示例：

输入：root = [1, null, 2, 3]
        1
         \
          2
         /
        3
输出：[1, 2, 3]

递归解

前序遍历的定义本身就是递归的：先访问根，再递归左子树，再递归右子树。三行代码：

class Solution:
    def preorderTraversal_recursive(self, root):
        result = []

        def dfs(node):
            if node is None:
                return
            result.append(node.val)                # 根
            dfs(node.left)                         # 左
            dfs(node.right)                        # 右

        dfs(root)
        return result

复杂度 O(n) 时间、O(h) 空间（h 是树高，递归栈深度）。这份代码已是正解。但有两个工程上的问题。

递归栈深度：最坏情况是"链式"树（每个节点只有一个孩子），高度 = 节点数。LC 树题数据范围常给到 10⁴，链式树 10⁴ 高度直接超出 Python 默认递归深度 1000。

控制流不直观：递归隐藏了"系统调用栈"。面试官追问"不能用递归呢"时，需要把这个隐式栈显式化。

这就是为什么 LC 144 虽然简单，面试官十有八九让你写迭代版——验证你是否真的理解递归在做什么。

迭代解

直接套 §2 的前序迭代模板：显式栈，每次弹出一个节点访问，然后把"右孩子、左孩子"压进栈（右先压让左先弹）。代码已经在 §2 给出。

时间 O(n)，空间 O(h)。

关键细节：

• 压栈顺序"右 → 左"：栈 LIFO，左孩子后入先出。压反了得到"根 → 右 → 左"序。
• 空树要在迭代版手动判：if root is None: return [] 不能省。

Follow-up：前序的 V 在 L 之前。如果改成"V 夹在 L、R 之间"——左子树访问完才访问根——迭代怎么写？这是 §4.1 LC 94 中序遍历，得换 "push-all-left" 套路。

4. 例题

4.1 LC 94 二叉树的中序遍历

链接：LeetCode 94

题意：给一个二叉树的根节点 root，返回它节点值的中序遍历——按"左 → 根 → 右"的顺序访问每个节点。

数据范围：

• 节点数：0 到 100
• 节点值：-100 到 100

示例：

输入：root = [1, null, 2, 3]
        1
         \
          2
         /
        3
输出：[1, 3, 2]

中序的难点是：访问根的时机不在弹栈瞬间——你得先一路向左走到底、压栈，然后回头弹根、再处理右子树。

迭代模板：

class Solution:
    def inorderTraversal(self, root):
        result = []
        stack = []
        cur = root
        while cur is not None or stack:
            while cur is not None:                 # 一路向左压栈
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()                      # 弹出最左的根
            result.append(cur.val)                 # 访问根
            cur = cur.right                        # 转向右子树
        return result

复杂度 O(n) 时间、O(h) 空间。cur 是当前游标，外层 while 的条件 cur is not None or stack 意思是"还有路要走、或者栈里还有挂账"。

手动跑一遍：示例 [1, null, 2, 3]

    1
     \
      2
     /
    3

按上面的迭代代码逐步跟踪 cur / stack / result 三栏——每一步都是循环体内的一次完整 action：

终态 result = [1, 3, 2]，恰是中序。每个节点的 push / pop 各一次，总操作 2n，所以是 O(n)。

Morris 中序遍历：把空间砍到 O(1)

如果面试官追问"能不能用 O(1) 额外空间做中序遍历"，答案是 Morris 遍历。

核心想法：进入一个节点 cur 时，先找到它左子树的最右节点（也就是中序遍历中 cur 的前驱），把这个前驱的 right 指针临时指向 cur——这样左子树遍历完之后能"沿着假边"回到 cur。下次再回到这个前驱时，发现它的 right 已经指向 cur，说明左子树访问完了，把假边断开、访问 cur、转向右子树。

def morrisInorder(root):
    result = []
    cur = root
    while cur:
        if cur.left is None:
            result.append(cur.val)
            cur = cur.right
        else:
            pred = cur.left                        # 找左子树最右
            while pred.right and pred.right is not cur:
                pred = pred.right
            if pred.right is None:
                pred.right = cur                   # 建假边
                cur = cur.left
            else:
                pred.right = None                  # 拆假边
                result.append(cur.val)
                cur = cur.right
    return result

Morris 时间仍是 O(n)（每条边至多被遍历常数次），空间 O(1)。代价是临时改了树结构——并发环境或只读输入不能用。这是 O(1) 空间遍历的经典 trick，作为提示了解即可，本章不深入。

Follow-up：前序、中序都搞定了。如果不是按 DFS 顺序、而是要"按层"输出每一层的所有节点呢？

4.2 LC 102 二叉树的层序遍历

链接：LeetCode 102

题意：给一个二叉树的根节点 root，返回它的层序遍历结果——按层从上到下、每层从左到右访问所有节点。返回二维数组，每个子数组对应一层。

数据范围：

• 节点数：0 到 2000
• 节点值：-1000 到 1000

示例：

输入：root = [3, 9, 20, null, null, 15, 7]
        3
       / \
      9   20
          / \
         15  7
输出：[[3], [9, 20], [15, 7]]

层序遍历是 BFS。普通 BFS 不分层，所有节点按距离根的距离依次入队。这道题要"按层分组"——每层独立放一个子数组。

关键技巧：每轮 while 开始时，用 len(q) 锁定当前层的节点数，然后内层 for 循环正好处理这么多次。这样在内层 for 跑完之前，所有后入队的节点都属于下一层，不会被算进当前层。

from collections import deque

class Solution:
    def levelOrder(self, root):
        if root is None:
            return []
        result = []
        q = deque([root])
        while q:
            size = len(q)                          # 锁定当前层节点数
            level = []
            for _ in range(size):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(level)
        return result

复杂度 O(n) 时间、O(w) 空间（w 是树最大宽度，最坏 O(n/2)）。

为什么用 deque 而不是 list？Python 列表的 pop(0) 是 O(n)——它要把剩下所有元素左移。deque 的 popleft() 是 O(1)。BFS 里队列操作是热路径，必须 deque。

Java 用 ArrayDeque（offer / poll）或 LinkedList，C++ 用 queue<TreeNode*> 即可，底层默认 deque 已足够。

层序遍历是树题里最高频的考点之一——按层处理的题目非常多：右视图（每层最后一个）、锯齿形遍历（奇偶层方向不同）、最大宽度、最小深度……都是这套"锁定当前层"模板的变体。

5. 边界、易错与复杂度

空树

root == None / root == null / root == nil 是合法输入。递归版靠递归出口自动处理；迭代版要在循环前手动判。

漏判会导致"把 None 压栈、弹出来再访问 .val"——Python AttributeError、Java NullPointerException、C++ 段错误。

压栈顺序

迭代前序的压栈顺序是"右孩子、左孩子"——栈 LIFO，左孩子后入先出。压反了会得到"根 → 右 → 左"序。

迭代中序的"先一路向左压栈、再弹根、再转右"是固定套路，记住整个 while 结构。

list vs deque vs ArrayDeque

Java 千万别用 Stack——它是过时的同步类，性能差。ArrayDeque 同时可以当栈和队列用，是 Java 树题首选。

Python 别用 list.pop(0) 当队列——O(n) 操作，BFS 整体退化到 O(n²)。

递归 vs 迭代怎么选

• 题目数据范围 n ≤ 1000，语言是 Python / Java / C++ 都行：递归更简洁
• 数据范围 n > 10⁴，Python：默认栈深 1000，递归会爆栈，必须用迭代或 sys.setrecursionlimit(10**6)
• 面试官明确要"迭代版"：直接上 §2 模板
• 要 O(1) 空间：Morris 遍历，但要能改树结构

复杂度速查

h 是树高，最坏 O(n)（链式树）；w 是树的最大宽度，完全二叉树最坏 O(n/2)。

中序遍历的应用场景

中序遍历在二叉搜索树（BST）上有个特殊性质：得到的序列是严格递增的。很多 BST 题用中序遍历做检验或定位——比如 LC 98 验证 BST、LC 230 BST 第 k 小元素、LC 938 BST 范围和。这是后面 BST 章节的核心 trick。

7. 小结

二叉树遍历是树系列的入门骨架——三种 DFS 顺序加一种 BFS 层序，时间都是 O(n)，空间看实现。掌握三件事就能套绝大多数树题：

• 递归三件套：前/中/后只是"输出根值"的时机不同，结构完全一致。
• 迭代用栈：把系统调用栈显式化，避免 Python 默认深度限制。
• 层序用队列：len(q) 锁定当前层，所有"按层"变体都从这里发散。

下一节会进入树的结构性问题——递归比较两棵树、求最近公共祖先（LCA）、把序列反构造成树。