引言

大家好啊，我是前端拿破轮😁。

跟着卡哥学算法有一段时间了，通过代码随想录的学习，受益匪浅，首先向卡哥致敬🫡。

但是在学习过程中我也发现了一些问题，很多当时理解了并且AC的题目过一段时间就又忘记了，或者不能完美的写出来。根据费曼学习法，光有输入的知识掌握的是不够牢靠的，所以我决定按照代码随想录的顺序，输出自己的刷题总结和思考。同时，由于以前学习过程使用的是JavaScript,而在2025年的今天，TypeScript几乎成了必备项，所以本专题内容也将使用TypeScript，来巩固自己的TypeScript语言能力。

题目信息

144. 二叉树的前序遍历

94. 二叉树的中序遍历

145. 二叉树的后序遍历

题目分析

对二叉树的遍历最基本的操作，本文要分析的三种遍历都是属于深度优先搜索(DFS)。后续要介绍的二叉树的层序遍历则是广度优先搜索(BFS)。因为二叉树可以当作一种特殊的图。

对于二叉树的处理，往往有递归和迭代两种方式。理论上来讲，所有用递归实现的功能，都能用迭代等效实现，方式就是利用栈这种数据结构。因为计算机在运行递归代码时，也是在内部创建了递归调用栈从而实现递归遍历。如果能模拟递归调用栈的实现过程，就可以用迭代的方式来实现。本文拿破轮会分别介绍递归和迭代两种方式并分析其特点。

题解

递归法

很多同学总是一入递归深似海，从此offer是路人。本质上是没有形成对递归类题目的方法论。递归问题可以按照如下的递归三部曲为例，进行分析：

  1. 确定递归函数的参数和返回值：首先要设计好函数需要的参数和要返回的值。这个不一定要局限于LeetCode的核心代码模式给出的函数，因为我们可以自定义一个函数，然后在题目给定的函数中调用我们自定义的函数即可。

  2. 确定递归的终止条件：在递归函数中一定要确定好终止条件，确保递归函数一定会结束时，否则会爆栈产生栈溢出的错误。

  3. 确定单层递归的逻辑：拿破轮个人觉得这块是最难的，因为这一部分是我们要对某一层递归的具体处理，也就是在这一部分中，我们会调用递归函数自己。关于这块，拿破轮的技巧是，只分析最开始一步的递归逻辑，因为第一步往往是最简单的。

我们来以前序遍历为例，来说明具体如何操作。

下面是leetcode给出的核心代码模式的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function preorderTraversal(root: TreeNode | null): number[] {
    
};

注释告诉我们，已经定义好了TreeNode这个类，我们可以直接调用使用。

并且给出了我们函数preorderTraversal，也已经明确了参数和返回值，参数是一个TreeNode节点，最开始传入的肯定是根节点。返回值是一个number型的数组，保存前序遍历顺序的节点值。

这个函数可不可以直接用作递归的函数呢？在这个题目中是可以的。所以第一步已经完成了，即确定函数的参数和返回值。

第二步就是确定终止条件，什么时候终止呢？当当前节点是null时，就终止。问题是，终止时应该返回什么呢？直接return吗？直接return意味着返回的是undefined。这合不合适呢？还是看第一步，我们确定的返回值是一个数组。所以如果当前节点是null，应该返回空数组。

第三步就是确定单层递归的逻辑，这一步是最难的，也是最关键的核心逻辑，在这一步要调用递归函数自身，但是该何时调用，如何调用？还是需要好好思考的。我们思考这道题目的目的，就是给你一棵二叉树，然后返回一个数组，里面是这个二叉树节点值的前序遍历的结果。我们需要注意的是，二叉树的左右子树也是一棵二叉树。所以，说确定单层递归逻辑最简单的方式就是，只看第一层的递归。什么叫做只看第一层递归呢，就是我只分析最开始加入的根节点。由于二叉树的左右子树也是二叉树，所以先对左右子树调用递归函数，这样就可以得到左右子树的前序遍历结果数组。至于具体怎么得到的，我们就不去考虑了，我们只考虑第一层递归，就是得到之后再怎么操作，才能得到根二叉树的最终结果。首先左右子树返回的都是一个数组，里面是各自按先序遍历的结果，我们最后要返回的也是一个数组，这个数组中应该如下排序，才符合先序遍历的要求[根节点的值， 左子树先序遍历结果， 右子树先序遍历结果]。所以我们利用数组的展开运算符即可将最终结果返回。具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 迭代法前序遍历
function preorderTraversal(root: TreeNode | null): number[] {
  // 确定终止条件
  if (root === null) return [];

  // 得到左子树的结果,具体怎么得到不用关心
  const left = preorderTraversal(root.left);

  // 同理得到右子树的结果
  const right = preorderTraversal(root.right);

  // 想一想，得到这些结果后，最终的返回值应该是怎么样的
  return [root.val, ...left, ...right];
};

前序遍历处理完，中序和后序就是同样的道理，很简单了。

只需要考虑最后一步，拿到左右子树的结果后，应该如何返回最终结果？

前序是[根节点的值, 左子树结果, 右子树结果]

中序是[左子树结果, 根节点的值, 右子树结果]

后序是[左子树结果, 右子树结果, 根节点的值]

所以代码如下，不再进行过多解释。

1
2
3
4
5
6
7
8
9
10
11
12
// 中序递归遍历
function inorderTraversal(root: TreeNode | null): number[] {
    // 终止条件
    if (root === null) return [];

    // 单层递归逻辑
    return [
        ...inorderTraversal(root.left),
        root.val,
        ...inorderTraversal(root.right)
    ]
};
1
2
3
4
5
6
7
8
9
10
11
12
// 后序递归遍历
function postorderTraversal(root: TreeNode | null): number[] {
    // 终止条件
    if (root === null) return [];

    // 单层递归逻辑
    return [
        ...postorderTraversal(root.left),
        ...postorderTraversal(root.right),
        root.val
    ]
};

迭代法

相比于递归法，迭代法代码要更复杂，也相对来说要难理解一些。刚才在递归法中，我们直接对左右子树调用递归函数来拿到遍历的结果数组，而并不关心具体如何实现的。但是在递归法中，相当于我们要手动控制整个子树的遍历过程。

在递归法中，我们首先要明确，我们需要一个辅助栈来存储遍历过的节点。此外，对于所有的节点，都要经过两个过程，一个是访问，一个是处理。所谓的访问，就是指针遍历到它，并将其压入栈中。所谓的处理，是指将其节点的值加入结果数组。为什么会这样呢？难道不能在访问的时候，直接将其加入结果数组吗？确实不行，因为如果给定我们一棵二叉树，实际上就是给出其根节点。也就意味着我们第一个访问的一定是根节点，但是遍历顺序中，只有前序遍历是要求先遍历根节点的，其他的遍历方式都不是。所以访问和处理的逻辑一定要分开，这也是迭代法最关键的点。

我们以前序遍历为例，分析迭代法的实现。首先我们还是需要进行剪枝，如果根节点为空，则直接返回空数组。

然后，我们需要一个辅助栈。将根节点压入栈中。在辅助栈非空时，弹出栈顶节点进行处理，将其值加入结果数组。那么之后呢？之后应该如何处理？前序遍历要求的顺序是根左右。很多同学可能觉得现在处理完根节点了，接下来应该处理左子树，所以将左子树的根节点压入栈中，实际上恰恰相反，我们应该将右子树的根节点压入栈中。这是因为栈的后进先出的LIFO，所以我们要先压入右子树的根节点，再压入左子树的根节点，这样在处理的时候才能先弹出左子树的根节点。

这里一定要注意，我们必须得确保左右节点非空时才能压入栈中，否则栈中就会出现null，从而导致错误。为什么递归法就不用呢？原因是递归法我们已经在终止条件中进行了处理，当根节点为null时返回空数组。有同学可能说，我们迭代法，在最开始不是也有类似的剪枝操作吗？为什么这里还得确保左右节点有值才能加入呢？要注意，迭代法中，我们的遍历逻辑是在while循环中控制的，而不是整个函数，所以最开始的剪枝操作只会作用于最开始的根节点，后续的子树并不会生效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 二叉树的前序遍历迭代法
function preorderTraversal(root: TreeNode | null): number[] {
    // 结果数组
    const result: number[] = [];

    // 剪枝
    if (root === null) return result;

    // 辅助栈
    const stack: TreeNode[] = [];

    // 将根节点入栈
    stack.push(root);

    // 当辅助栈非空时开始遍历
    while (stack.length) {
        // 弹出栈顶元素
        const p = stack.pop();

        // 将当前值加入结果数组
        result.push(p.val);

        // 如果有右孩子，压入
        p.right && stack.push(p.right);

        // 如果有左孩子，压入
        p.left && stack.push(p.left);
    }
    return result;
};

由于迭代法的遍历需要我们自己控制逻辑，所以前中后序遍历的差别还是挺大的。不是像递归法一样简单换一下最后的位置就可以。

那中序遍历应该怎么做呢？中序要求左根右。但我们最先访问的却是根节点，这可怎么办呢？我们需要一个额外的指针来访问元素，而不是与处理顺序相同。先让指针指向根节点，如果当前元素非空或者栈非空的时候，进行迭代。如果当前元素非空，说明我们还没有走到最左边的节点。所以将当前元素压入栈中，然后移动指针，指向左孩子。如果当前元素为空，说明我们已经走到最左边，所以要进行回溯。把栈顶元素弹出，栈顶元素就对应左根右中的根。将其值加入结果数组。然后就需要右了，所有将指针再指向右孩子。他会自动重复while循环，即可完成遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 迭代法中序遍历
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function inorderTraversal(root: TreeNode | null): number[] {
    // 结果数组
    const result: number[] = [];

    // 剪枝
    if (root === null) return result;

    // 辅助栈
    const stack: TreeNode[] = [];

    // 当前指针
    let cur = root;

    // 当指针非空或辅助栈非空时，开始迭代
    while (stack.length || cur) {
        // 如果指针非空
        if (cur) {
            // 将当前指针所指元素加入栈中
            stack.push(cur);

            // 移动指针
            cur = cur.left;
        } else {
            // 如果指针非空，则弹出栈顶元素
            const p = stack.pop();

            // 将值加入结果数组
            result.push(p.val);

            // 指针移动向右孩子
            cur = p.right;
        }
    }
    // 返回结果数组
    return result;
};

那后序遍历要求的是左右根又应该怎么操作呢？如果直接想，确实会更加复杂。因为先访问左节点，再访问右节点，最后才访问根节点这个其实和二叉树的结构是不符合的。因为从根节点可以轻松访问到左右子节点，利用栈，也可以实现从左节点或右节点访问回父节点。但是直接从左节点访问的到右节点是比较困难的。所以后序遍历要使用一个巧妙的的办法。后序遍历的要求是左右根反过来不就是根右左吗？和前序遍历的区别只有左右子树的访问顺序不同。所以我们只需要按前序的方式遍历，但是在压入的时候，修改为先压入左孩子，再压入右孩子。最后将结果数组翻转后返回即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 迭代法后序遍历
function postorderTraversal(root: TreeNode | null): number[] {
    // 结果数组
    const result: number[] = [];

    // 剪枝
    if (root === null) return result;

    // 辅助栈
    const stack: TreeNode[] = [];

    // 压入根结点
    stack.push(root);

    // 当栈非空时开始迭代
    while (stack.length) {
        // 弹出栈顶元素
        const p = stack.pop();

        // 值加入结果数组
        result.push(p.val);

        // 先左后右
        p.left && stack.push(p.left);
        p.right && stack.push(p.right);
    }
    // 返回翻转后的结果
    return result.reverse();
};

总结

二叉树的前中后序遍历都属于深度优先搜索DFS，在遍历上都有递归和迭代两种方式。递归方式代码简介且理解后控制起来更容易。迭代方式则需要控制遍历的具体细节，比较容易出错。两种方式我们都应该掌握，从而对二叉树有更深刻的认识。

好了，这篇文章就到这里啦，如果对您有所帮助，欢迎点赞,收藏,分享👍👍👍。您的认可是我更新的最大动力。由于笔者水平有限，难免有疏漏不足之处，欢迎各位大佬评论区指正。

往期推荐✨✨✨

我是前端拿破轮，关注我，一起学习前端知识，我们下期见！