leetcode 二叉树遍历全解:DFS、BFS、双色标记与 Morris 遍历的完整实现

原创2026-09-18 09:04:171,894 阅读
文章标签:教程文档知识库

leetcode 二叉树遍历全解:DFS、BFS、双色标记与 Morris 遍历的完整实现

本文基于 leetcode 题解仓库的专题笔记 二叉树的遍历(中文版见 thinkings/binary-tree-traversal.md),系统讲解二叉树的五种遍历实现方式:前序、中序、后序、层序,以及能够统一三种深度优先遍历的双色标记法和 O(1) 空间的 Morris 遍历。读完之后,你将能够针对任意二叉树题目快速选择递归或迭代方案,理解栈与递归的对应关系,并掌握按层输出的标记位技巧。

一、总览:遍历是树题目的底层能力

二叉树作为基础数据结构,遍历作为基础算法,两者的结合产生了大量经典问题。很多题目中都有树遍历的身影——有的是直接考察遍历本身,有的是间接考察:例如要求“找到树中满足条件的节点”时,本质上就要求你先完成一次遍历。

如果掌握了二叉树的遍历,那么其他更复杂的树(多叉树、森林等)对你来说也大概率不再困难。

仓库将二叉树遍历划分为两大类:

  • 深度优先遍历(DFS):前序(Preorder)、中序(Inorder)、后序(Postorder),三者的差别仅在于根节点被访问的相对位置,左右子树的相对顺序永远是“先左后右”;
  • 广度优先 / 层次遍历(BFS):逐层、从左到右访问节点。中文版笔记补充了一个值得记住的观点:层次遍历其实可以看成“没有提前终止的 BFS”,因此它既可以用 BFS 实现,也可以用 DFS 实现,只是 BFS 更容易写。

DFS 与 BFS 都各有典型应用。仓库中可参考的两个例子是 301. 删除无效的括号(用 BFS 按删除次数分层搜索,保证找到删除数量最少的解)和 609. 在系统中查找重复的文件(用 DFS 递归目录结构)。

对于 DFS,有两个关键点:

  1. 栈:迭代实现 DFS 时,栈用于保存“待访问但暂不能输出”的节点;
  2. 递归:树本身就是递归定义的数据结构(树 = 根 + 左子树 + 右子树),递归是 DFS 最自然的表达方式。

对于 BFS,关键点是如何判断每一层的遍历已经完成。答案是引入一个特殊标记(仓库题解中使用 null)作为当前层结束的标识。

DFS 遍历过程图解(来自 DFS 动画):

二叉树深度优先遍历(DFS)动画

二、前序遍历(Preorder):根 - 左 - 右

前序遍历的顺序是 根 - 左 - 右,对应题目 144. 二叉树的前序遍历。

2.1 栈迭代算法

由于是“根”先访问,前序迭代实现是所有 DFS 遍历中最直观的:

  1. 访问根节点,将其压入栈;
  2. 弹出一个节点,将其右子节点、左子节点依次压入栈(注意入栈顺序:右先左后,这样左子节点会先被弹出);
  3. 重复步骤 2,直到栈为空。

仓库中 144 号题解 给出的 JavaScript 迭代实现完整体现了这一算法:

// 迭代方案:先根、再左、最后右
if (!root) return [];
const ret = [];
const stack = [root];          // 1. 根节点入栈
let t = stack.pop();

while (t) {
  if (t.right) {
    stack.push(t.right);       // 2. 右子先入栈(后出)
  }
  if (t.left) {
    stack.push(t.left);        // 左子后入栈(先出)
  }
  ret.push(t.val);             // 访问当前节点
  t = stack.pop();
}

return ret;

同文件还提供了另一种风格的 C++ 实现(problems/144.binary-tree-preorder-traversal.md#L119-L133):沿左链一路压栈并输出,遇到空指针时回退到栈顶的右子树——这种写法与中序遍历的结构非常接近,是理解“迭代与递归互转”的好素材。

2.2 宏观视角:自上而下递归 + 自底向上用栈

如果把前序遍历放到更大的尺度上看,它的过程可以描述为:自顶向下依次访问左侧链,然后自底向上依次访问右侧链。

二叉树前序遍历过程示意

  • “自上而下”的部分可以直接用递归完成;
  • “自底向上”的部分则交给栈。

从源码结构看,这种思路与回溯法(backtrack)的处理方式非常相似:递归负责进入子问题,栈负责在返回时重建现场。仓库中专门有一篇 回溯法笔记 展开讨论,而更重要的是:“自上而下 + 自底向上”的视角可以统一前、中、后三种 DFS 遍历,这是本专题最值得记住的一个结论。

三、中序遍历(Inorder):左 - 根 - 右

中序遍历的顺序是 左 - 根 - 右,对应题目 94. 二叉树的中序遍历。

与前序不同,根节点不是第一个输出的,因此不能简单地“弹栈即输出”。栈迭代算法如下:

  1. 访问根节点,将其压栈;
  2. 如果存在左子节点,将其压栈,重复此过程直到到达叶子节点——此时栈中保存的是从根到最左叶子的一整条左链(即“根节点和所有左节点都在栈中”);
  3. 开始弹出栈顶节点;若该节点有右子节点,则右子节点入栈,回到步骤 2 继续。

94 号题解 的 Python 迭代实现是该算法的忠实翻译:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        stack = []
        ans = []
        cur = root

        while cur or stack:
            # 步骤 2:沿左链压栈,直到 cur 为空
            while cur:
                stack.append(cur)
                cur = cur.left
            # 步骤 3:弹出并访问,转向右子树
            cur = stack.pop()
            ans.append(cur.val)
            cur = cur.right
        return ans

同文件还给出了等价的 JavaScript 与 Java 版本(94 号题解),三者的骨架完全一致:while cur or stack → 压左链 → 弹出访问 → 转右子树。

3.1 BST 的重要性质

值得特别指出的是:二叉搜索树(BST)的中序遍历结果是一个有序数组。这一性质可以让不少 BST 相关题目得到简化,例如:

四、后序遍历(Postorder):左 - 右 - 根

后序遍历的顺序是 左 - 右 - 根,对应题目 145. 二叉树的后序遍历。

这一题在 LeetCode 上带 Hard 标签,难度在于根节点最后输出:一个节点只有在两种情况下才能出栈输出——

  1. 它是叶子节点(left 与 right 同时为 null,判断很直接);
  2. 它的左、右子树都已经遍历过了。

对于条件 2,最朴素的做法是为每个节点都记录一个访问状态,空间复杂度 O(n)。但仓库笔记指出一个更聪明的观察:我们使用的是栈、且输出从叶子开始,因此只需要记录“上一个出栈输出的节点”这一个变量即可判断栈顶的子树是否已完成遍历,空间复杂度降为 O(1)(不计算输出数组与递归/栈本身)。

145 号题解 的 JavaScript 实现中,变量 p 就是这一技巧的落地:

if (!root) return [];
const ret = [];
const stack = [root];
let p = root; // 标识元素,用来判断节点是否应该出栈

while (stack.length > 0) {
  const top = stack[stack.length - 1];
  if (
    top.left === p ||
    top.right === p ||                  // 子节点已经遍历过了
    (top.left === null && top.right === null) // 叶子元素
  ) {
    p = stack.pop();
    ret.push(p.val);                    // 满足输出条件,出栈并记录
  } else {
    if (top.right) stack.push(top.right);
    if (top.left)  stack.push(top.left);
  }
}

return ret;

注意循环里并没有每次无条件弹栈:当栈顶节点不满足输出条件时,只压入它的左右子节点并继续观察——这正是“记录当前节点是否已访问”思想的体现。同文件的 C++ 版本用 prev 指针完成了同样的逻辑(145 号题解)。

五、层次遍历(Level Order / BFS)

层次遍历的关键点与总览部分提到的完全一致:如何判断每一层的遍历已经完成。仓库的做法是往队列中放入一个特殊标记 null 来表示当前层的结束。

BFS 遍历过程图解(来自 BFS 动画):

二叉树广度优先遍历(BFS)动画

算法步骤(对应题目 102. 二叉树的层序遍历):

  1. 访问根节点,将其放入 FIFO 队列,同时向队列放入一个特殊标记(此处使用 null);
  2. 出队一个节点;
  3. 若该节点等于 null,说明当前层所有节点已访问完。再判断队列:若队列已空则什么都不做(遍历结束);否则再放入一个 null,为下一层准备结束标记;
  4. 若该节点不是 null,说明当前层还没遍历完,将它的左、右子节点依次入队。

102 号题解 的 JavaScript 实现:

var levelOrder = function (root) {
  if (!root) return [];
  const items = [];           // 存放所有层的结果
  const queue = [root, null]; // null 作为每层的结束标记
  let levelNodes = [];        // 存放当前层的节点值

  while (queue.length > 0) {
    const t = queue.shift();

    if (t) {
      levelNodes.push(t.val);
      if (t.left)  queue.push(t.left);
      if (t.right) queue.push(t.right);
    } else {
      // 一层遍历完了:结算当前层,为下一层准备标记
      items.push(levelNodes);
      levelNodes = [];
      if (queue.length > 0) {
        queue.push(null); // 注意:必须先判断队列非空,否则会无限循环
      }
    }
  }

  return items;
};

题解中还给出了一个等价的替代方案(C++ 迭代版):不在队列中放入 null,而是在每轮 while 循环开始时先记录当前队列长度 sz,然后只处理 sz 个节点,从而天然地按层切分结果。两种方案时间复杂度都是 O(N)O(N),空间复杂度 O(N)O(N)(N 为节点总数)。

另外提醒一个容易踩的坑:题解的关键点解析中明确写道——“塞入 null 的时候,判断一下当前队列是否为空,不然会无限循环”。

层次遍历的直接变体是锯齿形层次遍历(103. 二叉树的锯齿形层次遍历):遍历过程与 102 完全相同,只是奇数层(从 0 计)将结果倒序输出,题解中用 isOdd 标志位控制 reverse(),见 103 号题解。

六、双色标记法:用一种写法统一三种 DFS 遍历

垃圾回收算法中存在“三色标记法”,其颜色语义为:

  • 白色:尚未访问;
  • 灰色:尚未完全访问子节点;
  • 黑色:子节点已全部访问。

受其启发,仓库笔记发明了双色标记法(两个状态足够),用同一套框架解决前、中、后三种 DFS 遍历:

  • 用颜色标记节点状态:新节点为白色(WHITE = 0),已访问节点为灰色(GRAY = 1);
  • 遇到白色节点:将其标记为灰色,然后依次压入栈的是 右子节点、自身(灰色)、左子节点;
  • 遇到灰色节点:输出它的值。

原文档给出的中序遍历实现:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        WHITE, GRAY = 0, 1
        res = []
        stack = [(WHITE, root)]
        while stack:
            color, node = stack.pop()
            if node is None: continue
            if color == WHITE:
                # 白色:压入 右(白) -> 自身(灰) -> 左(白)
                stack.append((WHITE, node.right))
                stack.append((GRAY, node))
                stack.append((WHITE, node.left))
            else:
                res.append(node.val)
        return res

前序、后序遍历只需调整三个元素压栈的顺序(即调整 右/自身/左 的相对顺序)即可得到,这就是“统一三种遍历”的具体含义。中文版笔记进一步点出了其本质(thinkings/binary-tree-traversal.md):WHITE 对应递归中“第一次进入节点”的过程,GRAY 对应“从叶子节点返回”的过程,因此这种迭代写法最接近递归的本质,便于记忆和书写;代价是线性额外空间,但由于递归栈开销的常数项更大,实际差异有限——双色迭代法是一种用迭代模拟递归的写法,比普通迭代写法简单得多。

七、Morris 遍历:O(1) 空间的遍历

还有一种既不递归、也不用栈的遍历方式:Morris 遍历。

先更正一个细节:英文版原文写作“time complexity is O(1)”,这与中文版“从而在 O(1)O(1) 空间完成这个过程”(thinkings/binary-tree-traversal.md)相互对照可以判断,正确表述应为时间复杂度 O(n)、空间复杂度 O(1)——每个节点最多被访问两次、每条边最多被走过两次,因此时间是线性的;空间上只用了常量个指针。原文档给出的 Python 实现如下:

def MorrisTraversal(root):
    curr = root

    while curr:
        # If left child is null, print the
        # current node data. And, update
        # the current pointer to right child.
        if curr.left is None:
            print(curr.data, end= " ")
            curr = curr.right

        else:
            # Find the inorder predecessor
            prev = curr.left

            while prev.right is not None and prev.right is not curr:
                prev = prev.right

            # If the right child of inorder
            # predecessor already points to
            # the current node, update the
            # current with it's right child
            if prev.right is curr:
                prev.right = None
                curr = curr.right

            # else If right child doesn't point
            # to the current node, then print this
            # node's data and update the right child
            # pointer with the current node and update
            # the current with it's left child
            else:
                print (curr.data, end=" ")
                prev.right = curr
                curr = curr.left

其原理可以这样理解:当需要访问某节点 curr 的右子树时,先找到其左子树中的中序前驱(左子树中最右的节点)。若前驱的 right 尚未指向 curr,说明左子树还没走完,先“打一条临时线索”(prev.right = curr)再进入左子树;若已指向 curr,说明左子树已遍历完毕,拆除线索(恢复 prev.right = None)再进入右子树。整个算法通过对树做 O(n) 次可逆的临时修改换取了 O(1) 空间。

仓库的总结是:如果题目要求 O(1) 空间遍历二叉树,就要想到 Morris 遍历。该算法在刷题中考察频率不高,作为了解即可;它同样存在一个副作用——会临时修改树结构,因此不适用于不允许修改输入树的场景。

八、选型建议与相关题目

结合本仓库的专题脉络(thinkings/binary-tree-traversal.md 与 树专题),可以归纳如下选型策略:

场景 推荐方案 空间复杂度
常规遍历 / 数据规模不大 递归(DFS) O(h),h 为树高
需要迭代且要“统一三种遍历” 双色标记法 O(n)
前序 / 中序 / 后序的常规迭代 显式栈 O(n)
层序、锯齿层序、按层处理 BFS + null 标记位(或记录层长度) O(n)
题目明确要求 O(1) 空间 Morris 遍历 O(1)
需要实现“迭代器”(每次调用输出一个值) 文中介绍的显式栈迭代方式,把状态保存在栈中即可 O(h)

仓库中与本专题强相关的题目文件,可作为练习序列:

最后回到开篇的那句话:前中后三序遍历之间变的只是根节点的位置,左右顺序永远是先左后右;而“自上而下递归 + 自底向上用栈”的视角,是把这些差异收敛到同一套框架里的钥匙。掌握了二叉树的遍历,再面对多叉树、森林或带权树时,需要补充的只是孩子节点的组织方式,而遍历的思想可以完全复用。

登录后查看全文
leetcode