深入解析：Leetcode 30

1 题目

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序遍历。

示例 1：

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

输出：[1,2,3]

解释：

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

解释：

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法搞定吗？

2 题解

递归算法

首先我们需要了解什么是二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要首先将 root 节点的值加入答案，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。代码

void preorder(struct TreeNode* root, int* res, int* resSize) {
    if (root == NULL) {
        return;
    }
    res[(*resSize)++] = root->val;
    preorder(root->left, res, resSize);
    preorder(root->right, res, resSize);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 2000);
    *returnSize = 0;
    preorder(root, res, returnSize);
    return res;
}

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

【int* res, int* resSize什么意思？】

把二叉树所有节点的值按「根 - 左 - 右」的顺序存起来，返回给调用者。就是先，这段代码是用来达成「二叉树的前序遍历」的，目的

先看 int* res 是什么？

res 是一个「指向整数的指针」，可以理解为一个「动态数组」，用来存储遍历到的节点值。比如，遍历到根节点，就把根节点的值存到 res 里；再遍历左子树，把左子树的节点值依次存进去，最后存右子树的节点值。代码里用 malloc(sizeof(int) * 2000) 给它分配了内存（最多存 2000 个节点，题目约束里节点数不超过这个数）。

再看 int* resSize 是什么？

resSize 也是一个「指向整数的指针」，它的作用是记录当前 res 数组里已经存了多少个节点值（即数组的有效长度）。为什么要用指针？因为在递归函数里，我们需要修改该计数，并且让这个修改在函数外部也能生效。如果直接传整数，函数内部修改后外部不会变，而传指针就能保证内外的计数是同步的。

比如代码里的 res[(*resSize)++] = root->val 这句话：

• 先取 resSize 指向的整数（当前有效长度），作为 res 数组的下标，把当前节点值存进去；
• 然后把这个计数加 1（++），表示数组里又多了一个元素。

举个例子理解

假设二叉树只有 3 个节点：根节点值为 1，左孩子 2，右孩子 3。

1. 开始时，res 是一个空数组，resSize 指向 0（表示目前存了 0 个元素）。
2. 遍历根节点 1：res[0] = 1，然后 resSize 变成 1（现在存了 1 个元素）。
3. 递归遍历左孩子 2：res[1] = 2，resSize 变成 2。
4. 递归遍历右孩子 3：res[2] = 3，resSize 变成 3。
5. 最后 res 数组里就是 [1,2,3]，resSize 指向 3，这个 3 会作为 returnSize 返回（告诉调用者数组长度）。

简单说：

• res 是装结果的 “容器”（数组）；
• resSize 是用来记录这个容器里已经装了多少个元素的 “计数器”（用指针是为了在递归中传递修改）。

【res[(*resSize)++] = root->val;//这一行没看懂】

这行代码是整个遍历过程中存储节点值的核心操作，我们拆成三步来看就容易理解了：

步骤 1：先解析 (*resSize)

resSize 是一个「指向整数的指针」，*resSize 表示 “取这个指针指向的整数”。这个整数的含义是：当前 res 数组中已经存储了多少个节点值（即数组的有效长度）。

比如，一开始 *resSize 是 0（还没存任何值），存了一个值后变成 1，以此类推。

步骤 2：再看 res[(*resSize)]

res 是存储结果的数组，res[索引] 表示访问数组中对应索引的位置。这里的索引就是 *resSize，意思是：把当前节点的值存到数组的 “下一个空位”。比如，*resSize 是 0 时，就存到 res[0]；是 1 时，存到 res[1]，正好接在已有元素后面。

步骤 3：最后是 (*resSize)++

这是一个 “后置自增” 处理，意思是：先使用当前的 *resSize 值，用完之后再把它加 1。结合前面的步骤就是：先用 *resSize 作为索引存值，存完之后，把这个计数加 1，方便下一次存储时使用新的索引。

举个具体例子

假设现在 *resSize 是 2（已经存了 2 个值），当前节点值是 5。执行 res[(*resSize)++] = root->val 时：

1. 先取 *resSize 的值 2，作为索引，执行 res[2] = 5（把 5 存到数组的第 3 个位置，因为索引从 0 开始）；
2. 存完之后，*resSize 自动加 1，变成 3（表示现在数组里有 3 个值了）。

总结：这行代码的作用就是把当前节点的值，按顺序存到结果数组的下一个空位，同时更新数组的有效长度。整个操作一步到位，相当简洁！

递归】就是【在定义的preorder里面调用preorder，这就

递归的核心思想就是「自己调用自己」，用解除子问题的方式来解决原问题。

在这段代码里，preorder 函数的作用是：遍历以 root 为根的二叉树，并把节点值按前序顺序存入 res 数组。

为什么可以在 preorder 里调用 preorder 呢？我们结合二叉树的结构来看：

二叉树的每个节点，其左子树和右子树本身也是一棵二叉树（可以称为「子问题」）。比如：

• 当我们遍历完当前节点 root 后，需要遍历它的左子树，而遍历左子树的逻辑和遍历整个树的逻辑完全一样（都是「根 - 左 - 右」），所以直接调用 preorder(root->left, res, resSize) 即可。
• 同理，左子树遍历完后，再用同样的逻辑遍历右子树，即调用 preorder(root->right, res, resSize)。

这样一层一层地「自己调用自己」，直到遇到空节点（root == NULL），就不再递归（终止条件），然后逐步返回，最终完成整个树的遍历。

举个简单的例子：如果有棵树是 root(1) 左孩子 2，右孩子 3，那么执行流程是：

1. 调用 preorder(1, res, resSize)，先存 1，然后调用 preorder(2, ...)。
2. 调用 preorder(2, ...)，存 2，然后调用 preorder(2的左孩子，...)，发现是 NULL，返回。
3. 回到 preorder(2, ...)，再调用 preorder(2的右孩子，...)，发现是 NULL，返回。
4. 回到 preorder(1, ...)，继续调用 preorder(3, ...)，存 3，后续左右孩子都是 NULL，返回。
5. 整个过程结束，res 里就是 [1,2,3]。

这就是递归的巧妙之处：用相同的逻辑处理不同规模的子问题，直到问题小到可以直接解决（空节点时返回）。

94. 二叉树的中序遍历 - 力扣（LeetCode）

145. 二叉树的后序遍历 - 力扣（LeetCode）

理解了这两题一下就写完了！