0144. Binary Tree Preorder Traversal
====================================
题目信息
--------
:题号: 0144. 二叉树的前序遍历
:难度: Easy
:主题: 二叉树、深度优先搜索、显式栈、Morris 线索化
:原题: `LeetCode 0144 `_
:重点: 从递归的根左右顺序提取待处理子树状态,再用临时回边进一步消除栈并保证树结构恢复
题目重述
--------
给定二叉树根节点 ``root``,返回前序遍历结果。对每棵非空子树,先访问根节点,再完整遍历左子树,最后完整
遍历右子树;每个结构节点访问一次,即使节点值相同也要分别输出。空树返回空数组。
自建示例
--------
* ``root = [6, 2, 9, null, 4, 7, null]``:访问顺序为 ``6, 2, 4, 9, 7``;
* 只有右链 ``1 -> 2 -> 3``:每个节点没有左子树,结果为 ``[1, 2, 3]``;
* 空树返回 ``[]``,单节点树返回只含根值的数组。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
void recursivePreorder(
TreeNode* node,
std::vector& result
) {
if (node == nullptr) {
return;
}
result.push_back(node->val);
recursivePreorder(node->left, result);
recursivePreorder(node->right, result);
}
std::vector preorderWithStack(TreeNode* root) {
std::vector result;
if (root == nullptr) {
return result;
}
std::stack pending;
pending.push(root);
while (!pending.empty()) {
TreeNode* node = pending.top();
pending.pop();
result.push_back(node->val);
if (node->right != nullptr) {
pending.push(node->right);
}
if (node->left != nullptr) {
pending.push(node->left);
}
}
return result;
}
std::vector preorderWithMorrisThreads(TreeNode* root) {
std::vector result;
TreeNode* current = root;
while (current != nullptr) {
if (current->left == nullptr) {
result.push_back(current->val);
current = current->right;
continue;
}
TreeNode* predecessor = current->left;
while (predecessor->right != nullptr &&
predecessor->right != current) {
predecessor = predecessor->right;
}
if (predecessor->right == nullptr) {
result.push_back(current->val);
predecessor->right = current;
current = current->left;
} else {
predecessor->right = nullptr;
current = current->right;
}
}
return result;
}
public:
std::vector preorderTraversal(TreeNode* root) {
return preorderWithStack(root);
}
};
题解
----
递归为什么天然得到前序
~~~~~~~~~~~~~~~~~~~~~~
``recursivePreorder`` 进入非空节点后立即记录根值,随后依次调用左、右孩子。函数调用栈隐式保存了尚未处理
的工作:进入左子树时,当前节点的右子树和返回位置仍留在栈帧中。每个节点只有唯一父路径,因此无需访问
集合;空指针分支只表示没有子树,不产生输出。
这种写法最贴近定义,时间 ``O(n)``,但高度为 ``h`` 的树需要 ``O(h)`` 调用栈。要改成迭代,必须显式保存
相同的“已经发现但尚未访问的子树根”。
显式栈的不变量与压入顺序
~~~~~~~~~~~~~~~~~~~~~~~~
``pending`` 中保存待执行前序遍历的子树根,栈顶是下一棵应处理的子树。弹出 ``node`` 时先输出它,完成
“根”;随后把孩子加入待处理集合。由于栈后进先出,必须先压右孩子、再压左孩子,左孩子才会下一次弹出:
.. code-block:: text
弹出 root,输出 root
压入 root.right
压入 root.left
下一次弹出 root.left
当左子树继续压入自己的节点时,它们始终位于原右子树之上,所以完整左子树会先完成。若反过来先压左再压
右,得到的是根、右、左,不是前序。
具体走读待处理栈
~~~~~~~~~~~~~~~~
对 ``[6, 2, 9, null, 4, 7, null]``,栈顶写在右侧:
.. list-table::
:header-rows: 1
* - 弹出并输出
- 压栈动作
- 操作后待处理栈
* - ``6``
- 先 ``9``,后 ``2``
- ``[9, 2]``
* - ``2``
- 只有右孩子 ``4``
- ``[9, 4]``
* - ``4``
- 无孩子
- ``[9]``
* - ``9``
- 压左孩子 ``7``
- ``[7]``
* - ``7``
- 无孩子
- 空
输出恰为 ``6, 2, 4, 9, 7``。这里栈保存的是待访问节点,不是已访问节点,也不需要额外阶段标记,因为前序
在第一次遇到根时就输出。
如何连显式栈也省掉
~~~~~~~~~~~~~~~~~~
处理一个有左子树的节点后,遍历必须在左子树结束时回到当前节点,再进入右子树。递归栈和显式栈都在保存
这个“返回当前节点”的续点。Morris 遍历利用左子树最右节点 ``predecessor`` 原本为空的 ``right``,临时
令它指回 ``current``,把返回地址编码进树的空指针。
第一次找到 ``predecessor->right == nullptr`` 时,说明当前根尚未处理:前序应立刻输出根,建立临时回边,
再进入左孩子。以后沿左子树遍历到最右端,会通过回边重新到达 ``current``;第二次查找发现
``predecessor->right == current``,说明左子树已经完成,此时删除回边并进入原右子树,根不能再次输出。
没有左孩子的节点可直接输出并走右边。这个右指针可能是真实右孩子,也可能是祖先建立的临时线索;两种
情况都代表前序中的正确下一步。
临时修改为何不会破坏树
~~~~~~~~~~~~~~~~~~~~~~
每条 Morris 线索只写入原本为空的 ``predecessor->right``,并且同一当前节点第二次到达时立即恢复为空。
正常遍历结束后所有线索都成对建立和删除,原树结构完全恢复。寻找前驱会沿部分右链两次,但每条相关边只
被常数次经过,总时间仍为 ``O(n)``,不是嵌套循环表面上的 ``O(n^2)``。
主解选择与复杂度
~~~~~~~~~~~~~~~~
公开入口采用显式栈:时间 ``O(n)``,工作空间最坏 ``O(h)`` 至 ``O(n)``,不修改输入树,状态也最易审查。
递归版同为 ``O(h)`` 栈但更简洁;Morris 版将输出数组之外的空间降为 ``O(1)``,代价是遍历期间暂时改变
指针,对只读、并发访问或可能中途异常退出的环境不合适。三种方案分别展示隐式续点、显式续点和树内续点,
具有真实的状态演进。