一，用栈实现二叉树先序遍历

1，原理

我用自己的口水话解释一下：准备一个栈，从根节点开始，先判断栈是否为空，如果否，就弹出一个元素，对弹出元素进行自定义处理，再将它的左右子节点压入栈内，重复操作。

因为是先序，所以弹出节点后应该先压入右节点，再是左节点。

会发现在没有处理完左节点之前，右节点不会弹出。

AI版：

1. 代码逻辑

• 逻辑正确：代码通过栈模拟了先序遍历的递归过程。先序遍历的顺序是：访问当前节点 -> 遍历左子树 -> 遍历右子树。为了确保正确顺序，栈中的节点应该先推入右子树，再推入左子树。因为栈是后进先出（LIFO）的结构，所以右子树会先被弹出，左子树会后被处理。

• 栈操作：你正确地检查了 temp->right 和 temp->left 是否为 NULL，然后将其推入栈中。因为栈是LIFO（后进先出）结构，必须先把右子树压入栈，再把左子树压入栈。这样就可以确保左子树先于右子树被访问。

2，代码

a，第一次

void preOrder_traverse(TreeNode* current)
{stack<TreeNode*> stack;TreeNode* temp;stack.push(current);while (!stack.empty()){temp = stack.top();stack.pop();cout << temp->value << " ";if (temp->right != NULL) stack.push(temp->right);if (temp->left != NULL) stack.push(temp->left);}
}

改进：

2.1 避免不必要的空检查

在遍历二叉树时，如果当前节点为空，通常不需要进行遍历。你在检查 temp->left != NULL 和 temp->right != NULL 后才将它们推入栈。其实可以简化一下，直接压栈而不需要显式的空检查，因为栈会自动跳过空指针。

2.2 优化栈操作

你当前的代码通过 stack.push 和 stack.pop 操作栈，这是标准做法，但可以稍微优化，减少某些不必要的操作，例如直接将 current 节点放入栈而不是单独创建 temp 变量。

二，中序遍历

 1，原理

传入一个节点，先压入自己，然后处理自己的左子树，一直压入左节点，直至为空，然后返回后，弹出自己，再处理自己的右子树。

2，代码

a，第一次尝试

不知道哪里有问题

void inOrder_traverse(TreeNode* root)
{stack<TreeNode*> stack;TreeNode* current = root;if (current == NULL){cout << " the tree is empty !" << endl;return;}while (root != NULL || !stack.empty()){if (current != NULL){stack.push(current);current = current->left;//实现访问节点的左移。}else{current = stack.top();//返回到上一个节点。左序遍历结束，回到原节点进行操作，再访问右节点。cout << current->value << " ";stack.pop();current = current->right;//节点右移，再进行一次while循环，右节点又开始遍历左子树。}}
}

改进：

1. 空树检查的位置

在函数开始时，你检查了树是否为空，并且直接返回了一个提示信息。虽然这可以防止对空树进行遍历，但它的做法不是很优雅。遍历本身可以通过 root == NULL 的条件自然停止，因此可以移除这部分早期的输出消息，直接返回。

2. 循环条件的改进

在 while (root != NULL || !stack.empty()) 中，你使用了 root != NULL 作为条件之一。这个条件在第一次循环时是多余的，因为你已经在循环内部通过 current != NULL 来处理遍历。

3. 提升可读性

虽然代码是正确的，但可以稍微优化一些地方，使它更加简洁和易于理解。例如，在第一次进入循环时，可以直接将 current 赋值为 root，不需要特别的判断。

4. 代码结构的优化

避免冗余的条件判断，使代码结构更加简洁。

重要改进：

1. 简化 while 循环：将左子树的遍历逻辑放入内部的 while (current != NULL) 循环中，这样就避免了对 if (current != NULL) 和 else 的冗余判断。遍历左子树时，将节点压栈，一直向左移动。

void inOrder_traverse(TreeNode* root)
{stack<TreeNode*> stack;TreeNode* current = root;if (current == NULL){cout << " invalid input !" << endl;return;}while (current != NULL || !stack.empty()){while(current != NULL){stack.push(current);current = current->left;//实现访问节点的左移。}current = stack.top();//返回到上一个节点。左序遍历结束，回到原节点进行操作，再访问右节点。cout << current->value << " ";stack.pop();current = current->right;//节点右移，再进行一次while循环，右节点又开始遍历左子树。}
}

三，后序遍历

使用栈实现二叉树的后序遍历（Post-order Traversal）是比中序遍历和先序遍历更具挑战性的，因为在后序遍历中，需要先访问左子树，再访问右子树，最后访问根节点。递归版本的后序遍历容易实现，但使用栈时，需要注意节点的访问顺序。

后序遍历的基本顺序：

1. 先遍历左子树。
2. 然后遍历右子树。
3. 最后访问根节点。

使用栈来实现后序遍历时，我们通常会用两个栈来解决问题，或者通过修改栈的操作来模拟递归的调用栈。

使用栈实现后序遍历的思路：

1. 一个栈的方式：

   • 通过栈来模拟递归的过程。我们会使用一个额外的标记来标识节点的访问顺序。
   • 直接模拟后序遍历的过程，会比较复杂，因为后序遍历需要根节点最后访问。栈的特点是“后进先出”，所以需要调整栈的使用策略。

2. 两个栈的方式：

   • 使用一个栈进行深度优先搜索，遍历树的节点并将节点压入栈中。
   • 然后将这些节点的值反转输出，这样可以实现后序遍历的顺序。

两个栈实现后序遍历

使用两个栈实现后序遍历的基本步骤是：

1. 使用第一个栈遍历整个树并将节点压栈。
2. 将第一个栈中的节点弹出并按照后序的顺序处理节点。
3. 最后一个栈的输出顺序即为后序遍历的顺序。

步骤：

1. 使用一个栈来处理节点。首先将根节点压入栈中。
2. 将栈中的节点弹出时，首先将根节点的左右子树压入栈。
3. 将访问的顺序反转，确保根节点最后访问。

我的思路是：

准备两个栈，一个栈用于访问树，称为stack；另一个栈用于保存输出访问的顺序，称为collect。

stack用于处理访问过程，我们已知后序遍历顺序是：左右中。利用栈先进后出的特点，进入collect栈的顺序就应该是中右左，那么为了从stack到collect栈。处理一个节点流程是：先压入该节点，然后弹出放入collect里面。再将该节点的左右子节点压入stack里面，（注意：先左后右）

你压入的节点又像第一次压入的节点一样，进行弹出压入左右子节点。

为了方便理解：举个节点深度为1的，那么就是先压入根节点，弹出根节点压入collect，再往stack里面压入根节点的左右子节点，重复根节点的操作。

1，代码：双栈实现

第一次尝试：

void posOrder_traverse(TreeNode* root)
{TreeNode* current = root;stack<TreeNode*> stack, collect;if (current == NULL){cout << "invalid input !" << endl;return;}stack.push(current);while (!stack.empty())//获取后序遍历输出顺序,储存在collect栈里面。{current = stack.top();stack.pop();collect.push(current);if(current->left != NULL) stack.push(current->left);if(current->right != NULL) stack.push(current->right);}TreeNode* temp;while (!collect.empty()){temp = collect.top();collect.pop();cout << temp->value << " ";//自定义操作。}
}

注意检查压入stack栈的节点是否为空，我不知道为什么我不加，代码在VS上运行就没有结果。

AI提出的改进

你的代码基本思路是正确的，使用了两个栈来实现二叉树的后序遍历，其中一个栈 stack 用于存储节点，另一个栈 collect 用于存储节点的遍历顺序，最终通过弹出 collect 栈中的节点来输出后序遍历结果。下面我会分析和解释一些细节，以及为什么在将节点压入栈时需要判断节点是否为空。

1. 代码分析和问题解释

1.1 栈 collect 的作用

• 你的代码通过 collect 栈来收集节点，以便最后按后序遍历的顺序输出。
• 在 stack 栈中，先将根节点压栈，然后遍历左右子树。你将节点压入 collect 栈是为了反转遍历的顺序，这样可以确保节点的输出顺序是后序遍历的顺序。

1.2 为何需要判断 current->left 和 current->right 是否为空

• 当你调用 stack.push(current->left) 或 stack.push(current->right) 时，如果某个节点为空（NULL），你依然会将其压入栈中，但这没有意义。NULL 节点不会对后续操作有任何作用，所以需要跳过这些为空的节点。

• 如果你不进行空判断，压入 NULL 节点会导致栈中存在无用元素，浪费了栈的空间，而且后续对这些 NULL 节点的操作（比如弹出）将没有任何实际意义。

  例如：

  • 当一个节点没有左子树时，current->left 为 NULL，直接将 NULL 压入栈中会导致后续对栈的访问时处理 NULL 节点，这时会误操作，浪费栈的空间。

1.3 优化建议：

• 避免压入空指针：在压栈之前应该确保 current->left 和 current->right 都不为空。
• 改进代码：你可以在压栈时进行空检查，从而避免将空节点压入栈。

2，代码：单栈实现

a，第一次尝试

void posOrder_traverse(TreeNode* root)
{if (root == NULL){cout << "invalid input !" << endl;return;}TreeNode* current, * mark = NULL;//两个指针，分别用于指向正在处理的节点和已经处理过的节点。current = root;stack<TreeNode*> stack;stack.push(root);while (!stack.empty()){current = stack.top();//这一步实现访问节点更新，现在将current->left赋值给currentif (current != NULL &&mark != current->left &&mark != current->right)//就是该节点是第一次访问，接下来该先访问其左，再是右，最后才是自身。{if(current->left != NULL) stack.push(current->left);//需要判断压入的指针是否为空，避免浪费空间，同时防止后面对空指针访问其value}else if (current != NULL &&mark != current->right)//这是节点的左子树被处理了，该访问右子树，访问的操作就是将节点压入栈中{if(current->right != NULL) stack.push(current->right);}else{mark = stack.top();//先标记要处理的节点cout << mark->value << " ";//这里是自定义操作。stack.pop();//处理后的节点就弹出栈。}//当该节点的左右子树都处理完后，终于开始访问其本身时。}
}

不知道为啥，就是不对。

终于，自己一步步模拟代码运行过程发现，这是访问到节点5之前的过程：

模拟过程

假设当前 root 是根节点 1，mark 为 NULL，栈内只有根节点 1。

1. 初始化：

   • stack.push(root)，栈内有 [1]。
   • 当前 current = 1，mark = NULL。

2. 第一轮循环：

   • 栈顶是 1，所以 current = 1。
   • current 不是 NULL，并且 mark 没有指向它的左右子树，所以进入第一个 if 判断：
     • current->left != NULL，即 2 存在，所以压入栈中：stack.push(2)。
   • 栈变为 [1, 2]。

3. 第二轮循环：

   • 栈顶是 2，所以 current = 2。
   • current 不是 NULL，并且 mark 没有指向它的左右子树，所以进入第一个 if 判断：
     • current->left != NULL，即 4 存在，所以压入栈中：stack.push(4)。
   • 栈变为 [1, 2, 4]。

4. 第三轮循环：

   • 栈顶是 4，所以 current = 4。
   • current 不是 NULL，并且 mark 没有指向它的左右子树，所以进入第一个 if 判断：
     • current->left 为 NULL，所以没有压入左子树。
     • current->right 为 NULL，所以没有压入右子树。
   • 4 的左右子树都处理完了，现在进入 else：
     • mark = 4，输出 4，然后弹出栈：stack.pop()。
   • 栈变为 [1, 2]。

5. 第四轮循环：

   • 栈顶是 2，所以 current = 2。
   • current != NULL 且 mark != current->left，即 mark != 4，所以进入 else if 判断：
     • mark = 4，mark != current->right，即 mark != 5，所以将右子树 5 压入栈：stack.push(5)。
   • 栈变为 [1, 2, 5]。

注意：当到达节点5的时候，因为此时mark为4，会导致一直进入if条件判断，且因为stack没有压入新的元素，所以current一直没有更新，陷入死循环。

不知道对不对。

突然看视频教程发现自己弄错了关键的部分，重新写一下。

原理：

当访问某一节点时，无论是第一次，还是再次，都要判断左右子节点有没有处理或者遍历过。

即看current的left和right是否等于mark，如果没有就像左子树移动，将左节点压入栈中。

当左子树被处理或为空后，开始压入右子节点。更新current。

我犯错的点是我判断当前节点是否为空了，导致遇到上面像节点5这种叶节点时陷入死循环。

代码：

void posOrder_traverse(TreeNode* root)
{if (root == NULL){cout << "invalid input !" << endl;return;}TreeNode* current, * mark = NULL;//两个指针，分别用于指向正在处理的节点和已经处理过的节点。current = root;stack<TreeNode*> stack;stack.push(root);while (!stack.empty()){current = stack.top();//这一步实现访问节点更新，现在将current->left赋值给currentif (current->left != NULL && mark != current->left && mark != current->right)//就是该节点是第一次访问，接下来该先访问其左，再是右，最后才是自身。{stack.push(current->left);}else if (current->right != NULL && mark != current->right) stack.push(current->right);//完美的处理了右子树，当右子节点为叶节点时。else{mark = stack.top();//先标记要处理的节点cout << mark->value << " ";//这里是自定义操作。stack.pop();//处理后的节点就弹出栈。}//当该节点的左右子树都处理完后，终于开始访问其本身时。}
}

四，复杂度分析

1，后序遍历分析

对于使用双栈实现，虽然好写，但是空间复杂度不好，要创建两个栈。

2，时间复杂度

a，递归方法

任何节点，都会访问三次。如果有n个节点，访问3n次，时间复杂度就是o（n）。

b，非递归方法

也是o（n）。每个节点基本上是进栈一次，出栈一次。

3，空间复杂度

无论递归还是非递归，空间复杂度都是o（h），h是树的高度。之前使用的空间在弹出后可以回收利用的。

五，拓展：Morris遍历

我下次再写，先留下基础概念

Morris 遍历是一种不需要使用栈或递归的二叉树遍历算法，利用二叉树的空闲指针来实现遍历，特别适合用于空间复杂度要求较低的情况。

Morris 遍历的基本思想

Morris 遍历通过将二叉树的空闲指针（即右子树指针）临时改为指向父节点来模拟栈的行为。这样做的好处是，我们可以在常数空间内实现二叉树的遍历，而不需要额外的栈或递归调用。Morris 遍历主要分为前序遍历和中序遍历两种实现方式。

Morris 前序遍历

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

算法步骤：

1. 当前节点 current 为空时，遍历结束。
2. 如果当前节点没有左子树：
   • 直接访问当前节点，并移动到右子树。
3. 如果当前节点有左子树：
   • 找到当前节点的左子树的最右节点（即左子树的最右边节点，或者左子树中最深的右子节点）。这称为“线索化”。
   • 将该最右节点的右指针指向当前节点（这就是 Morris 遍历的“线程”）。
   • 然后将当前节点移动到它的左子树继续遍历。
4. 当左子树遍历完后，恢复右指针，移到当前节点的右子树继续遍历。

void morrisPreorderTraversal(TreeNode* root) {TreeNode* current = root;while (current != NULL) {if (current->left == NULL) {// 访问当前节点cout << current->value << " ";current = current->right;} else {// 找到左子树的最右节点TreeNode* pred = current->left;while (pred->right != NULL && pred->right != current) {pred = pred->right;}// 如果最右节点的右指针为空，则将其指向当前节点if (pred->right == NULL) {cout << current->value << " ";  // 访问当前节点pred->right = current;  // 创建线程current = current->left;  // 移动到左子树} else {// 恢复最右节点的右指针pred->right = NULL;current = current->right;  // 移动到右子树}}}
}