0094. Binary Tree Inorder Traversal
===================================
题目信息
--------
:题号: 0094. 二叉树的中序遍历
:难度: Easy
:主题: 二叉树、深度优先遍历、显式栈、Morris 遍历
:原题: `LeetCode 0094 `_
:重点: 从递归控制流推导显式栈,再用中序前驱线索把辅助空间压缩到常数级
题目重述
--------
给定二叉树根节点 ``root``,按照“左子树、根节点、右子树”的顺序返回所有节点值。
空树返回空数组。
树中节点数在 ``0..100`` 范围内,节点值在 ``-100..100`` 范围内。
自建示例
--------
.. code-block:: text
输入(层序):[4,2,6,null,3,5,7]
输出:[2,3,4,5,6,7]
先访问根节点 4 的左子树 ``2,3``,再访问 4,最后访问右子树 ``5,6,7``。
.. code-block:: text
输入(层序):[3,2,null,1]
输出:[1,2,3]
左斜树需要不断深入左侧,随后按从深到浅的顺序访问祖先。
.. code-block:: text
输入:[]
输出:[]
空树没有可访问节点。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
void inorderDfs(TreeNode* node, std::vector& result) {
if (!node) {
return;
}
inorderDfs(node->left, result);
result.push_back(node->val);
inorderDfs(node->right, result);
}
std::vector recursiveTraversal(TreeNode* root) {
std::vector result;
inorderDfs(root, result);
return result;
}
std::vector explicitStack(TreeNode* root) {
std::vector result;
std::vector stack;
TreeNode* current = root;
while (current || !stack.empty()) {
while (current) {
stack.push_back(current);
current = current->left;
}
current = stack.back();
stack.pop_back();
result.push_back(current->val);
current = current->right;
}
return result;
}
std::vector morrisTraversal(TreeNode* root) {
std::vector result;
TreeNode* current = root;
while (current) {
if (!current->left) {
result.push_back(current->val);
current = current->right;
continue;
}
TreeNode* predecessor = current->left;
while (predecessor->right && predecessor->right != current) {
predecessor = predecessor->right;
}
if (!predecessor->right) {
predecessor->right = current;
current = current->left;
} else {
predecessor->right = nullptr;
result.push_back(current->val);
current = current->right;
}
}
return result;
}
public:
std::vector inorderTraversal(TreeNode* root) {
return explicitStack(root);
}
};
题解
----
递归定义
~~~~~~~~
中序遍历的定义本身就是一个递归过程:先完成左子树,再访问当前节点,最后完成右子树。
递归调用进入左子树时,运行时栈会保存当前节点和返回后的执行位置。
.. code-block:: text
inorder(left)
visit(root)
inorder(right)
这种写法最接近定义,但最大递归深度等于树高。树退化为链时,调用栈需要 ``O(n)`` 空间。
显式保存祖先
~~~~~~~~~~~~
迭代方法把递归栈中“左子树尚未完成,因此当前节点暂时不能访问”的祖先显式保存到 ``stack``。
从 ``current`` 开始不断沿左指针下降,并把途经节点压栈。
当 ``current`` 变为空时,栈顶节点已经没有未处理的左后代,因此它就是下一个应访问的节点:
.. code-block:: text
沿左链压栈
弹出栈顶并访问
转向该节点的右子树
转入右子树后,循环再次展开它的完整左链,于是同一控制流可以处理任意树形。
栈状态不变量
~~~~~~~~~~~~
每次准备弹栈时,栈中从底到顶保存一条祖先路径。对栈顶节点而言:
* 左子树已经全部处理;
* 当前节点尚未输出;
* 右子树尚未处理。
弹出并输出节点后转向其右子树,正好把状态推进到中序遍历的下一阶段。
每个节点只会在沿左链下降时入栈一次,也只会弹出一次,因此不会重复访问。
示例过程
~~~~~~~~
对 ``[4,2,6,null,3,5,7]``,显式栈的关键状态如下:
.. list-table::
:header-rows: 1
* - 操作
- 栈(右端为栈顶)
- 输出
* - 沿左链压入 4、2
- ``[4,2]``
- ``[]``
* - 弹出 2,转向 3
- ``[4]``
- ``[2]``
* - 压入并弹出 3
- ``[4]``
- ``[2,3]``
* - 弹出 4,进入右子树
- ``[]``
- ``[2,3,4]``
* - 处理 6 的左节点 5,再处理 6、7
- ``[]``
- ``[2,3,4,5,6,7]``
Morris 线索
~~~~~~~~~~~
显式栈保存的是从左子树返回当前节点的路径。Morris 遍历利用左子树中原本为空的右指针,临时建立同样的返回线索。
当前节点存在左子树时,其中序前驱是左子树最右侧节点 ``predecessor``:
* 第一次找到前驱时,令 ``predecessor->right = current``,再进入左子树;
* 第二次沿线索回到当前节点时,恢复 ``predecessor->right = nullptr``,访问当前节点并进入右子树。
没有左子树的节点可以立即访问,因为它已经不存在更早的左侧节点。
结构恢复
~~~~~~~~
每条临时线索只会经历“空指针改为当前节点”和“恢复为空指针”两个阶段。
只有删除线索后才访问当前节点并进入右子树,因此遍历结束时所有被修改的指针都恢复为原值,树结构保持不变。
前驱搜索虽然会沿右链移动,但每条相关边只会在建立和删除线索时经过常数次。
所以 Morris 遍历仍是 ``O(n)`` 时间,并将除结果数组外的辅助空间降为 ``O(1)``。
方案选择
~~~~~~~~
递归方法最接近定义;显式栈不修改树结构,也避免依赖语言调用栈,是通用主解法。
Morris 遍历适合明确要求常数辅助空间的场景,但它会临时修改输入树,控制流和恢复要求更复杂。
复杂度
~~~~~~
三种方法都访问每个节点常数次,时间为 ``O(n)``。
递归与显式栈使用 ``O(h)`` 空间,``h`` 为树高;Morris 遍历除返回结果外使用 ``O(1)`` 空间。