25、树形结构的非递归算法：非递归遍历的深入、Morris遍历算法（线索化思想）
树形结构的遍历，递归写法是最直观的。但我在实际项目中，尤其是嵌入式系统或需要频繁遍历的场景下，递归往往不是最优解。为什么呢？递归调用会消耗栈空间，树一深，栈溢出风险就来了。今天我们就来聊聊非递归遍历的几种玩法，以及一个非常巧妙的算法——Morris遍历。
一、非递归遍历：用栈模拟递归
非递归遍历的核心思想，说白了就是手动维护一个栈，模拟系统栈的行为。你想想看，递归的本质不就是函数调用栈吗？我们自己用栈来管理节点，就能避免递归深度限制。
1. 前序遍历（非递归）
前序遍历的顺序是：根 -> 左 -> 右。非递归实现时，我们先把根节点入栈，然后循环处理：
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
Stack* stack = createStack();
push(stack, root);
while (!isEmpty(stack)) {
TreeNode* node = pop(stack);
printf("%d ", node->val);
// 注意：先右后左，因为栈是后进先出
if (node->right) push(stack, node->right);
if (node->left) push(stack, node->left);
}
destroyStack(stack);
}
这里有个小细节：为什么先压右子树再压左子树？因为栈是后进先出，我们希望左子树先被访问，所以后压入左子树。嗯，这个顺序搞反了，遍历结果就全乱了。
2. 中序遍历（非递归）
中序遍历稍微复杂一点，顺序是：左 -> 根 -> 右。我们需要一直往左走，直到走不动了，再处理当前节点，然后转向右子树。
void inorderTraversal(TreeNode* root) {
Stack* stack = createStack();
TreeNode* curr = root;
while (curr != NULL || !isEmpty(stack)) {
// 一直往左走，把沿途节点压栈
while (curr != NULL) {
push(stack, curr);
curr = curr->left;
}
// 弹出栈顶节点，访问它
curr = pop(stack);
printf("%d ", curr->val);
// 转向右子树
curr = curr->right;
}
destroyStack(stack);
}
我曾经在调试一个表达式求值程序时，就用了这个中序遍历的非递归版本。当时递归版本在表达式树深度超过1000层时直接崩溃，换成非递归后稳如老狗。
3. 后序遍历（非递归）
后序遍历是最麻烦的，顺序是：左 -> 右 -> 根。难点在于：访问根节点之前，必须确保左右子树都访问完了。我们需要记录上一个访问的节点来判断。
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
Stack* stack = createStack();
TreeNode* curr = root;
TreeNode* lastVisited = NULL;
while (curr != NULL || !isEmpty(stack)) {
// 往左走到底
while (curr != NULL) {
push(stack, curr);
curr = curr->left;
}
TreeNode* peekNode = peek(stack);
// 如果右子树为空，或者右子树已经访问过，就访问当前节点
if (peekNode->right == NULL || peekNode->right == lastVisited) {
printf("%d ", peekNode->val);
lastVisited = pop(stack);
} else {
// 否则，转向右子树
curr = peekNode->right;
}
}
destroyStack(stack);
}
注意：后序遍历的非递归实现中，lastVisited 变量是关键。没有它，你永远不知道右子树是否已经处理完毕。我见过不少新手在这里栽跟头。
二、Morris遍历算法：不用栈的遍历
前面讲的非递归遍历，虽然避免了递归深度问题，但依然需要 O(h) 的额外空间（h 是树的高度）。有没有一种方法，能做到 O(1) 空间复杂度？
答案是肯定的。Morris 遍历算法，利用线索化思想，通过修改树的结构来模拟递归过程。说白了，就是利用叶子节点的空指针，临时建立指向后继节点的线索。
1. Morris 中序遍历
Morris 中序遍历的核心思想是：对于每个节点，找到它左子树的最右节点（即中序遍历的前驱节点），然后把当前节点作为前驱节点的右孩子。这样，遍历完左子树后，就能通过这个线索回到当前节点。
void morrisInorder(TreeNode* root) {
TreeNode* curr = root;
TreeNode* predecessor = NULL;
while (curr != NULL) {
if (curr->left == NULL) {
// 左子树为空，直接访问当前节点
printf("%d ", curr->val);
curr = curr->right; // 转向右子树或线索
} else {
// 找左子树的最右节点（前驱）
predecessor = curr->left;
while (predecessor->right != NULL && predecessor->right != curr) {
predecessor = predecessor->right;
}
if (predecessor->right == NULL) {
// 建立线索：前驱的右指针指向当前节点
predecessor->right = curr;
curr = curr->left; // 继续向左走
} else {
// 线索已存在，说明左子树遍历完毕
predecessor->right = NULL; // 恢复树结构
printf("%d ", curr->val);
curr = curr->right; // 转向右子树
}
}
}
}
核心要点：Morris 遍历在遍历过程中会临时修改树的结构（建立线索），遍历完成后会恢复原状。所以它不会破坏原始树的结构。
2. Morris 前序遍历
前序遍历的 Morris 版本和中序遍历类似，只是访问节点的时机不同：在建立线索之前就访问当前节点。
void morrisPreorder(TreeNode* root) {
TreeNode* curr = root;
TreeNode* predecessor = NULL;
while (curr != NULL) {
if (curr->left == NULL) {
printf("%d ", curr->val);
curr = curr->right;
} else {
predecessor = curr->left;
while (predecessor->right != NULL && predecessor->right != curr) {
predecessor = predecessor->right;
}
if (predecessor->right == NULL) {
printf("%d ", curr->val); // 前序遍历：在建立线索前访问
predecessor->right = curr;
curr = curr->left;
} else {
predecessor->right = NULL;
curr = curr->right;
}
}
}
}
3. Morris 后序遍历
后序遍历的 Morris 实现稍微复杂一些，需要借助一个辅助函数来逆序输出路径。这里不展开细节，但核心思想是一样的：利用线索化思想，在遍历过程中记录路径。
三、三种遍历方式对比
| 遍历方式 | 递归 | 非递归（栈） | Morris |
|---|---|---|---|
| 空间复杂度 | O(h) | O(h) | O(1) |
| 时间复杂度 | O(n) | O(n) | O(n) |
| 是否修改树结构 | 否 | 否 | 临时修改，遍历后恢复 |
| 实现难度 | 简单 | 中等 | 较难 |
| 适用场景 | 树深度小 | 通用 | 内存受限环境 |
四、知识体系图
下面这张图展示了树形结构非递归遍历的完整知识体系：
五、避坑指南与个人经验
个人经验：我在一个嵌入式项目中，需要遍历一棵深度超过5000的树。递归版本直接栈溢出，非递归栈版本勉强能用，但内存占用偏高。最后换成 Morris 遍历，内存占用几乎为零，性能还提升了30%。
避坑指南：我曾经在 Morris 遍历中忘记恢复线索，导致树结构被永久破坏。后续操作全部出错，排查了整整一个下午。记住：Morris 遍历一定要在遍历完成后恢复所有线索（将前驱节点的右指针置回 NULL）。
另外，Morris 遍历虽然空间复杂度优秀，但时间复杂度常数项较大。因为每个节点最多被访问两次（一次建立线索，一次恢复线索）。如果你的树深度不大，用栈模拟的非递归遍历反而更快。
好了，关于非递归遍历和 Morris 算法，今天就聊到这里。这些技巧在实际开发中非常实用，尤其是当你面对资源受限的环境时。多写几遍代码，自然就熟练了。
公众号:蓝海资料掘金营，微信deep3321