leetcode 题解仓库中的二叉树遍历算法详解:DFS、BFS、双色标记法与 Morris 遍历

原创2026-09-18 09:07:501,626 阅读
文章标签:教程文档知识库

leetcode 题解仓库中的二叉树遍历算法详解:DFS、BFS、双色标记法与 Morris 遍历

二叉树遍历是树形数据结构最基础也最经典的算法族,在 leetcode 题解仓库 中,它被总结为一个独立专题(thinkings/binary-tree-traversal.md),并贯穿前序、中序、后序三种 DFS 遍历与层次遍历(BFS)四大主线。读完本篇,你将掌握四种遍历的完整迭代实现思路、统一的「自顶向下 + 自底向上」框架、用双色标记法统一三种遍历的技巧,以及 O(1) 空间 Morris 遍历的原理,并能把遍历能力迁移到 BST 验证、第 K 小元素等高频题型上。

前序遍历过程图解:自顶向下访问左侧链,自底向上访问右侧链

一、概述:DFS 与 BFS 两条主线

二叉树作为基础数据结构,遍历算法作为基础算法,两者结合是刷题中的经典组合:很多题目会直接或间接考察树的遍历——比如「找到树中满足条件的节点」这类题,本质上要求你先完成一次完整遍历。

仓库中的总结可以概括为三条主线:

  1. DFS 三条路线:前序(根-左-右)、中序(左-根-右)、后序(左-右-根)。前中后序属于深度优先遍历,它们变化的只是根节点的输出位置,左右子树的访问顺序永远是先左后右。
  2. 层次遍历:即 BFS,也可以理解为「没有提前终止的 BFS」——用队列即可实现,BFS 比 DFS 更适合表达层序语义。
  3. 两个关键点:DFS 可以用栈来简化操作;树本身是递归的数据结构,因此「递归」和「栈」是 DFS 的两个关键要素。这一点在仓库的 深度优先遍历专题 中也有呼应:DFS 中的 stack 可以理解为自实现的栈,也可以理解为语言的调用栈。

广度优先遍历(BFS)过程动画

DFS 与 BFS 各自都有典型应用,例如仓库题解中提到的 LeetCode 301 号问题(去除重复节点,基于栈的 DFS)与 609 号问题(基于 BFS 的重复子树识别),可以体会两种遍历的适用差异。

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

对应题目:144.binary-tree-preorder-traversal。

前序遍历的顺序是 根-左-右,因为根节点最先访问,迭代实现相对简单。核心思路(摘自仓库专题):

  1. 先将根节点入栈;
  2. 出栈一个元素,将其右节点和左节点依次入栈(注意入栈顺序是右先左后,这样左节点才能先出栈);
  3. 重复步骤 2。

仓库中给出的 JavaScript 迭代实现完整保留了「先处理当前节点、再压入子节点」的结构:

var preorderTraversal = function (root) {
  if (!root) return [];
  const ret = [];
  const stack = [root];
  let t = stack.pop();

  while (t) {
    if (t.right) {
      stack.push(t.right);
    }
    if (t.left) {
      stack.push(t.left);
    }
    ret.push(t.val);
    t = stack.pop();
  }

  return ret;
};

(代码取自 problems/144.binary-tree-preorder-traversal.md,时间复杂度 O(N),空间复杂度 O(N))

此外,仓库还指出了一种「宏观视角」的写法:前序遍历整体表现为自顶向下依次访问左侧链,然后自底向上依次访问右侧链。对应到代码上就是:从上向下用 while 循环不断压入左链并输出,从下向上借助栈弹出节点转向右子树。该仓库中 C++ 版本的迭代实现正是这种写法:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        vector<TreeNode*> s;
        while (root != NULL || !s.empty()) {
            while (root != NULL) {      // 自顶向下:一路压左链并输出
                v.push_back(root->val);
                s.push_back(root);
                root = root->left;
            }
            root = s.back()->right;    // 自底向上:弹出后转向右子树
            s.pop_back();
        }
        return v;
    }
};

这种写法的重要价值在于:它可以统一三种遍历的思路——前序、中序、后序只需要微调「输出时机」(见第三节)。

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

对应题目:94.binary-tree-inorder-traversal。

中序遍历的顺序是 左-根-右,根节点不是先输出,迭代实现因此比前序略复杂。仓库给出的步骤:

  1. 根节点入栈;
  2. 判断有没有左节点,如果有则继续入栈,直到叶子节点——此时栈中保存的就是所有左链节点加上根节点;
  3. 出栈一个节点(输出它),判断有没有右节点,有则入栈,回到步骤 2。

仓库中的多语言迭代实现,以 JavaScript 为例:

var inorderTraversal = function (root) {
  const res = [];
  const stk = [];
  while (root || stk.length) {
    while (root) {          // 一路把左链压栈
      stk.push(root);
      root = root.left;
    }
    root = stk.pop();        // 弹出即访问
    res.push(root.val);
    root = root.right;       // 转向右子树
  }
  return res;
};

(完整 JS/C++/Python/Java 四种语言实现见 problems/94.binary-tree-inorder-traversal.md)

BST 性质:中序遍历一棵二叉查找树(BST)的结果是一个有序数组。仓库中两个典型应用印证了这一点:

  • 230.kth-smallest-element-in-a-bst:沿中序遍历数到第 k 个节点直接返回即可,题解中给出了「计数到 k 提前终止」的迭代实现,还有基于子树节点计数剪枝的第二解法;
  • 98.validate-binary-search-tree:中序遍历过程中维护前驱节点 pre,一旦发现 cur.val <= pre.val 即判定不是 BST,避免了把整棵树结果存成数组。

这两道题的前置知识都标注为「中序遍历」,与遍历专题直接对应。

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

对应题目:145.binary-tree-postorder-traversal。

后序遍历的顺序是 左-右-根,也是三道经典遍历题中 LeetCode 难度最高的一道(Hard)。难点在于:根节点最后才输出,因此在迭代中不能像前序那样「出栈即输出」。仓库给出的讨巧做法是记录节点状态,满足以下任一条件才出栈输出:

  1. 当前节点是叶子节点(left 和 right 同时为 null);
  2. 当前节点的左右子树都已经遍历过(用一个变量记录上一个访问的节点即可,最坏情况才需要记录每个节点的访问状况,那样空间复杂度是 O(n),而只记录「上一个出栈元素」即可做到 O(1) 额外状态)。

仓库中的 JavaScript 实现完整体现了这个判断:

var postorderTraversal = function (root) {
  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++ 版本见 problems/145.binary-tree-postorder-traversal.md;C++ 版本用 prev 指针判断右子树是否已访问,同样只需 O(1) 额外状态)

五、层次遍历(BFS)

对应题目:102.binary-tree-level-order-traversal。

层次遍历的关键点在于如何记录每一层是否遍历完成。仓库给出的做法是「入队一个特殊标识位(null)表示本层结束」:

  1. 根节点入队列,同时入队一个特殊标识位(null);
  2. 出队列;
  3. 如果出队的是 null,代表本层已经结束:再次判断队列是否为空,不为空则继续入队一个 null,否则说明遍历完成,什么都不做(注意这里必须判空,否则会无限循环);
  4. 如果不为 null,说明本层还没完,将其左右子节点依次入队列。

仓库中的 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;
};

(代码见 problems/102.binary-tree-level-order-traversal.md,时间复杂度 O(N),空间复杂度 O(N))

仓库题解同时提供了两种替代方案,值得注意:

  • 不用 null 标识位:在 while 循环开始时保存当前队列长度 sz,每次只处理 sz 个节点,即天然完成一层(C++ 迭代版采用此法);
  • 递归方式:把当前节点、所在 level 以及结果数组传递给递归函数,按 level 把节点值追加到结果数组对应层(C++ 递归版与 Python 递归版采用此法)。

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

仓库专题最后介绍了模仿垃圾回收「三色标记法」思想的双色标记法:

  • 用颜色标记节点状态:新节点为白色,已访问的节点为灰色;
  • 如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈(入栈顺序恰好决定了出栈后的处理顺序);
  • 如果遇到的节点为灰色,则将节点的值输出。

仓库原文给出的中序遍历 Python 实现:

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

从实现上可以看出:WHITE 表示递归中的「第一次进入」过程,GRAY 表示递归中的「从子树返回」过程,因此这种迭代写法更接近递归的本质。要改成前序或后序遍历,只需要调整「右子节点、自身(GRAY)、左子节点」三者的入栈顺序即可。

仓库对此方法的评述是:写法类似递归形式,便于记忆和书写,缺点是使用了额外的线性内存空间;不过与递归相比,它只是每节点多存一个 0/1 颜色变量,空间复杂度的常数项更小(递归调用栈的单帧开销通常大于一个整型标记)。划重点:双色迭代法是一种用迭代模拟递归的写法,其写法和递归非常相似,要比普通迭代简单得多。

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

如果需要 O(1) 额外空间遍历一棵二叉树(既不用递归也不用栈),仓库介绍了 Morris 遍历:利用中序前驱节点的右指针为空这一特点,临时把它指向当前节点建立「线程」(thread),访问完左子树后再沿着线程回来并恢复指针,从而省去栈。仓库给出的 Python 实现(以原稿为准,属于先序输出形态的 Morris 遍历):

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

划重点:Morris 遍历是一种可以在 O(1) 空间遍历二叉树的算法。 仓库同时提示:该算法考察相对少,作为了解即可;另外需要注意它通过临时修改树指针实现,若树不可变或需并发访问则不适用。

八、总结与延伸

  • DFS 三个变体(前序/中序/后序)变化的是根节点输出位置,左右子树顺序永远是先左后右;迭代写法围绕「栈」展开,其中「自顶向下走左链 + 自底向上转右子树」的框架可以统一前序与中序,后序则需额外记录上一个访问节点来判断输出时机;
  • 层次遍历用队列 + 层末标识位(或层初队列长度)即可实现,本质是不带提前终止的 BFS;
  • 双色标记法用「入栈三件套(右、自身、左)」统一三种遍历,是比手写迭代更接近递归本质的记忆方式;Morris 遍历以 O(1) 空间为目标,作为了解即可;
  • 如果题目要求实现迭代器(每调用一次输出一个节点值),本文讲的迭代写法(尤其是中序遍历维护左链栈的写法)非常适用,典型如 BST Iterator 类题目;
  • 遍历能力是树题的地基:最近公共祖先、锯齿形层序遍历、验证二叉搜索树、最大深度、平衡二叉树、二叉树最大路径和等常见题型,都建立在这四种遍历之上。仓库中对应的题解可参考 124.binary-tree-maximum-path-sum、236.lowest-common-ancestor-of-a-binary-tree、103.binary-tree-zigzag-level-order-traversal、104.maximum-depth-of-binary-tree 等。

掌握二叉树遍历之后,其他更复杂的树形结构(如 N 叉树、Trie、线段树)的遍历方法也不远矣——它们无非是上述 DFS/BFS 框架在「节点子节点个数大于 2」场景下的自然推广。

登录后查看全文
leetcode