这是leetcode上的3个题目，要求用非递归实现，其中以后序遍历实现最难，既然递归实现的三种遍历程序只需要改变输入代码顺序，为什么循环不可以呢，带着这种执拗的想法，我开始了这次研究
我依然是将递归用栈来实现，而不打算使用改变二叉树结构的方法，那个我打算日后研究
首先以前序遍历为例
递归实现是：
void preorderTraversal(TreeNode* root) { if (root == nullptr) return; cout << root->val; preorderTraversal(root->left); preorderTraversal(root->right);} 利用循环和栈来实现递归
我的思路是每次循环对应一次函数调用，每次函数调用的root加入栈中，思考后，写出下面的程序
void preorderTraversal(TreeNode* root) { if (root == nullptr) return; stack sta; sta.push(root); while (!sta.empty()) { root = sta.top(); cout << root->val; if (root->left != nullptr) { sta.push(root->left); continue; } if (root->right != nullptr) { sta.push(root->right); continue; } sta.pop(); }} 但是经测试发现，这段程序有个巨大的漏洞，以至于无法结束循环，问题出现在pop某节点后，返回到父节点，会再次将该节点push到栈中，从而无限循环
对照递归的实现，脑补计算机函数进栈出栈的抽象图，发现计算机的函数堆栈绝非是保存root的栈可以替代的，它还保存了代码的执行位置，也就是栈指针和帧指针。
我们能否用变量保存上次循环执行的代码位置呢，我们可以设置一些tag标记来模拟栈指针。但是，这里还有更好的实现方法。
我们可以保存上次循环结束时的root节点，其名lastRoot，
如果lastRoot = root->left，则说明root->left已经遍历过一遍，不用再将其加入栈中，也就是下面的代码段不用再执行
if (root->left != nullptr) { sta.push(root->left); continue;} 如果lastRoot = root->right，则说明root->left和root->right都已经遍历过一遍，可以直接将root出栈，下面的代码段不用执行
if (root->left != nullptr) { sta.push(root->left); continue;}if (root->right != nullptr) { sta.push(root->right); continue;}
理解之后，不难写出代码，前序，中序，后续遍历的区别在于改变输出当前节点代码段的位置，同递归实现一样，只是顺序的区别，程序员就是这样懒，妄想一招鲜吃遍天下
// 前序遍历vector preorderTraversal(TreeNode* root) { vector out; if (root == nullptr) return out; stack sta; sta.push(root); TreeNode* lastRoot = root; while (!sta.empty()) { root = sta.top(); if(lastRoot != root->right) { if (lastRoot != root->left) { out.push_back(root->val); if (root->left != nullptr) { sta.push(root->left); continue; } } if (root->right != nullptr) { sta.push(root->right); continue; } } lastRoot = root; sta.pop(); } return out;}// 中序遍历vector inorderTraversal(TreeNode* root) { vector out; if (root == nullptr) return out; stack sta; sta.push(root); TreeNode* lastRoot = root; while (!sta.empty()) { root = sta.top(); if (lastRoot != root->right) { if (lastRoot != root->left) { if (root->left != nullptr) { sta.push(root->left); continue; } } out.push_back(root->val); if (root->right != nullptr) { sta.push(root->right); continue; } } lastRoot = root; sta.pop(); } return out;}// 后序遍历vector postorderTraversal(TreeNode* root) { vector out; if (root == nullptr) return out; stack sta; sta.push(root); TreeNode* lastRoot = root; while (!sta.empty()) { root = sta.top(); if (lastRoot != root->right) { if (lastRoot != root->left) { if (root->left != nullptr) { sta.push(root->left); continue; } } if (root->right != nullptr) { sta.push(root->right); continue; } } out.push_back(root->val); lastRoot = root; sta.pop(); } return out;}
另外还有其他实现方法，比如前序遍历，网上比较流行的方法是下面这种，这两种写法的思路是一样的，不过下面的要更简洁一些，虽然这种思路一开始我有些难以接受
不过还是要总结一下
1.选择一个root节点
2.将其左节点依次加入栈中
3.输出栈顶节点，弹出，然后将root设置为其右节点，重复1步骤
上面这些仅仅是程序的说明步骤，不能算是思路吧。不过要认真想一下的话，也许是跟人脑中遍历树的方式差不多，这里不做深入探讨。觉得麻烦的话，可以直接背上面总结的步骤。
vector preorderTraversal(TreeNode* root) { stack sta; vector out; while (root || !sta.empty()) { while (root) { sta.push(root); out.push_back(root->val); root = root->left; } if (!sta.empty()) { root = sta.top(); sta.pop(); root = root->right; } } return out;}// 另一种写法vector preorderTraversal(TreeNode* root) { stack sta; vector out; while (root || !sta.empty()) { if(root) { sta.push(root); out.push_back(root->val); root = root->left; } else { root = sta.top(); sta.pop(); root = root->right; } } return out;} 另外一种实现思路，这次栈中仅仅保存右节点，因为是前序遍历，左节点可以直接输出，注意，这种方法仅能用于前序遍历
vector preorderTraversal(TreeNode* root) { vector out; if (root == nullptr) return out; stack sta; sta.push(root); while (!sta.empty()) { out.push_back(root->val); if (root->right) sta.push(root->right); if (root->left) root = root->left; else { root = sta.top(); sta.pop(); } } return out;} 中序遍历其他方法（同前序遍历）：
vector inorderTraversal(TreeNode* root) { stack sta; vector out; TreeNode* cur = root; while (cur != nullptr || !sta.empty()) { if (cur != nullptr) { sta.push(cur); cur = cur->left; } else { cur = sta.top(); sta.pop(); out.push_back(cur->val); cur = cur->right; } } return out;} 后序遍历只能使用保存上次root节点的或tag标记的方法
后记：算法的研究深不见底，你总能从中发现新的东西，越是研究的深入，就越会发现我们平时习惯了的人类思维方式是多么神奇！