前序遍历
递归遍历的代码如下：
void preorderTraversalHelper(TreeNode *node, vector<int> &res) {
if (!node) return;
res.push_back(node->value);
preorderTraversalHelper(node->left); // 需要记录 node->left
preorderTraversalHelper(node->right); // 需要记录 node->right
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorderTraversalHelper(root, res);
return res;
}
按照递归前序遍历的想法，应当先处理当前树的根节点，再依次处理左子树和右子树。因此在非递归算法中，要记录还未处理的左子树和右子树，即node->left和node->right。
后续处理node->left时，又会产生新的树根，node->left->left和node->left->right，也需要记录。按照前序遍历，node->left->left和node->left->right在node->left之后、node->right之前被处理。因此，越新的树根越先被处理，适合用栈来保存需要记录的数据。
如果用栈s记录还未处理的树根，由于node->left和node->right都需要记录，由于先进后出的原理，应当先令node->right入栈，再令node->left入栈。因此，整个过程可以分为栈的初始化、处理栈中元素至栈空。后者是一个循环，循环体为：
- 从栈中弹出一个还未处理的树根
node； - 处理
node； - 将
node->right、node->left依次入栈。
由于循环终止的条件为栈空，所以在初始化时将root入栈。
按照上述分析，编写代码如下：
vector<int> preorderTraversal(TreeNode* root) {
std::vector<int> res;
std::stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
auto node = s.top();
s.pop();
if (!node) continue;
res.push_back(node->val);
s.push(node->right);
s.push(node->left);
}
return res;
}
也可以在入栈前检查入栈节点是否为nullptr，如果为空则不入栈。
观察到在循环体的末尾总是s的入栈操作，循环体的开始总是s的出栈操作，可以将其在循环体末尾合并为一步node = node->left。此时node需声明在循环体外：
vector<int> preorderTraversal(TreeNode* root) {
std::vector<int> res;
auto node = root;
std::stack<TreeNode*> s;
while (node || !s.empty()) {
if (!node) {
node = s.top();
s.pop();
continue;
}
res.push_back(node->val);
s.push(node->right);
node = node->left;
}
return res;
}
观察修改后的代码，可以看出栈中仅记录了node->right节点。对比递归版本的代码，可以想到，在node的处理过程中并没有修改node。因此，对node->left处理时直接由node得到即可。在不断处理node及node->left时函数栈（递归时）发生了变化，递归版本中node的变化可以通过函数栈展开恢复，但在非递归情况下无法恢复。所以仍然需要记录node->right。
实际上，第二个版本更接近递归代码中的栈辗转。由于前序遍历比较简单，可以不在外部显式使用node，但对于中序遍历和后序遍历，都需要显式使用node，等同于递归版本中的函数参数。
中序遍历
递归遍历的代码如下：
void inorderTraversalHelper(TreeNode *node, vector<int> &res) { // 1. 第一次使用 node
if (!node) return;
inorderTraversalHelper(node->left); // 2.
res.push_back(node->val); // 3. 第二次使用 node
inorderTraversalHelper(node->right); // 4. 需要记录 node->right
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorderTraversalHelper(root, res);
return res;
}
中序遍历也需要使用栈，与前序遍历类似。但中序遍历每个节点要路经两次，这两次需要执行的行为不一样，分别是遍历、处理。原因如下：
观察递归代码，在函数参数中1.处使用了一次node（遍历）；在2.处函数栈被覆盖（非递归情况下），node丢失；在3.处又再次使用了node（处理）。因此中序遍历需要记录node（已遍历但还未处理）。与前序遍历同理，node->right可以通过node得到，不需要记录。
中序遍历中处理栈的循环为：
-
node入栈（遍历）； - 若
node不为空，node = node->left，执行下一次循环体；否则，到步骤 3； - 分为三步：
- 元素出栈，赋给
node（第二次遇到该元素，应处理）； - 处理
node； -
node = node->right（按照递归次序，处理后遇到node->right，该遍历node->right）。
- 元素出栈，赋给
因此，函数体的入口表示遍历到node所代表的树，node入栈表示遍历，出栈是第二次遇到，应当处理，栈中保存的是已经遍历但还未处理的节点。代码如下：
vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> res;
std::stack<TreeNode*> s;
auto node = root;
while (node || !s.empty()) {
if (node) {
s.push(node);
node = node->left;
continue;
}
node = s.top();
s.pop();
res.push_back(node->val);
node = node->right;
}
return res;
}
观察到在循环体中若node一直不为空，将循环执行if语句体，可以修改循环体为：
while (node || !s.empty()) {
while (node) {
s.push(node);
node = node->left;
}
if (!s.empty()) {
node = s.top();
s.pop();
res.push_back(node->val);
node = node->right;
}
}
这里需要在while内再判断一次!s.empty()，各有千秋吧。
后序遍历
递归遍历的代码如下：
void postorderTraversalHelper(TreeNode *node, vector<int> &res) {
if (!node) return;
postorderTraversalHelper(node->left);
postorderTraversalHelper(node->right);
res.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorderTraversalHelper(root, res);
return res;
}
与中序遍历类似，每个节点要经过两次。按照中序遍历的思路，node->right可以通过node得到，因此只记录node。由于两者都是先处理左子树，因此循环体前半部分相同，但后半部分不一样。实际上这会遇到几个问题：
中序遍历的后半部分是出栈，得到之前的node，然后处理，再node = node->right遍历右子树。后序遍历如果也类似的话，那么就是：出栈，得到之前的node，再node = node->right遍历右子树，(#)，然后处理node。
问题一：在（#）处，node已经在遍历右子树时丢失了，没有机会再处理node。
解决方法：node不出栈，使用s.top()得到node->right，然后遍历右子树。但这时又有了问题二。
问题二：处理完右子树后依然再次考虑出栈，这时应该真正出栈然后处理node，如何分辨两种出栈动作？
解决方法：判断node == s.top()->right。如果成立，则当前已经处理完右子树，否则是处理完了左子树。
暂不考虑nullptr的问题，后序遍历中的循环体目前为：
-
node入栈（遍历）； - 若
node不为空，node = node->left，执行下一次循环体；否则，到步骤 3； - 分为：
- 若
node != s.top()->right（当前node为左子树），node = s.top()->right，执行下一次循环体；否则，到步骤 3.2； - 元素出栈，赋给
node（第二次遇到该元素，应处理）； - 处理
node。
- 若
问题三：在步骤 3.3 结束后，表示以node为根的树已经处理完毕。在新的循环开始处，node不能再次入栈。
解决方法：共有两种。一种方法是使用一个标志来判断当前node所代表的树是否已处理完毕（标志当前是否步骤 3.3 刚好完成），这个标志可以使用布尔值，也可以使用双指针cur和prev，然后判断cur和prev的关系。另一种方法可以由中序遍历的第二个版本得到，观察到步骤 3.3 完成后node代表的树已经处理完毕，那么当前node可能为父节点（s.top()）的左子树或右子树。若为左子树，则应该执行node = s.top()->right，否则应该继续按照node == s.top()->right进行处理。此时，步骤 3 完成后 node一定是当前还未遍历过的树，因此在循环体开始处入栈是正确的。
第二种方法的循环体如下（不考虑s.empty()）：
-
node入栈（遍历）； - 若
node不为空，node = node->left，执行下一次循环体；否则，到步骤 3； - 分为：
- 若
node == s.top()->right（当前node为右子树），元素出栈，赋给node（处理完右子树后该处理父节点）；否则到步骤 3.3（当前树为左子树，已处理完毕，应遍历右子树）； - 处理
node，到步骤 3.1（当前树已处理完毕，到步骤 3.1 判断当前树是左子树还是右子树）； -
node = s.top()->right。
- 若
第二种方法的代码如下：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> res;
std::stack<TreeNode*> s;
auto node = root;
while (node || !s.empty()) {
while (node) {
s.push(node);
node = node->left;
}
while (!s.empty() && node == s.top()->right) {
node = s.top();
s.pop();
res.push_back(node->val);
}
if (s.empty()) {
break;
}
else {
node = s.top()->right;
}
}
return res;
}
};
中序遍历和后序遍历的对比
中序遍历和后序遍历的循环体如下：
while (node || !s.empty()) { | while (node || !s.empty()) {
while (node) { | while (node) {
s.push(node); | s.push(node);
node = node->left; | node = node->left;
} | }
|
if (!s.empty()) { |
node = s.top(); | while (!s.empty() && node == s.top()->right) {
s.pop(); | node = s.top();
| s.pop();
res.push_back(node->val); | res.push_back(node->val);
| }
|
| if (s.empty()) {
| break;
| }
| else {
node = node->right; | node = s.top()->right;
| }
} |
} | }
可以看出它们都可以分为三部分：
-
node入栈，node = node->left； - 执行某些操作以处理
node； -
node = x->right。
步骤 1 为左子树节点一直入栈，但实际含义为刚开始遍历node，循环结束则表示 node所表示的子树已处理完毕；
步骤 2 执行中间步骤——处理完子树后该怎么办；
步骤 3 为到已经历过的节点的右节点，结束后到步骤 1. 表示开始遍历右子树。
对于中序遍历，中间步骤为，若当前处理完的是左子树，那么应该处理s.top()（父节点），处理之后父节点丢失（出栈），到步骤 3 遍历右子树；若当前处理完的是右子树，那么s.top()不再是父节点，因为父节点已经处理掉了，s.top()应当是右子树所在的一棵刚处理完的大左子树的父节点，因此按照处理完左子树的操作进行处理即可。所以不需要区分当前处理完的是左子树还是右子树。
对于后序遍历，中间步骤需要判断当前处理完的子树是左子树还是右子树，两者操作不同。若为左子树，则开始处理右子树，到步骤 3，父节点未出栈；否则为右子树，则开始处理父节点，处理完父节点后父节点应出栈，又是一棵树刚刚处理完，s.top()是父节点的父节点，重复步骤 2。