前言
二叉树用递归实现前中后序遍历虽然思路简单，但是由于OS分配给一个进程的栈空间很小，一般是8MB，在VS中，即便是release版本下，效率差别也不是很大。所以递归转非递归的原因不在于效率，而是递归有栈溢出的风险。
而进程被分配的堆空间大小能有几个G，所以在堆上模拟递归的过程能让递归的“层数”更深。通常使用循环和栈模拟递归，例如斐波那契数列可以用循环模拟递归，快排可以用栈模拟。
非递归模拟递归，最重要的是模拟递归的过程。
1. 二叉树的前序遍历
前序遍历的规则：根结点、左子树、右子树。这对每一个子树都是一样的，所以就整棵树而言，前序遍历最先访问的就是左路节点，接着就是左路节点的右子树。下面同样用cur表示当前遍历的结点。
想象递归的过程：每层栈帧都会保存cur的地址，当cur走到nullptr时，就会层层往上返回。那么我们可以用一个栈模拟栈帧存储cur的地址和返回的过程。
- 将左路结点全部入栈，入栈的同时访问结点的值，当cur遇到nullptr，即入栈完毕;
- 取栈顶结点top，即左路最深未被处理的结点，pop。对它的右子树重复步骤1p；
- 只要栈或cur至少有一个不为空，则说明还未遍历完毕，继续重复以上操作。
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { TreeNode* cur = root; vector<int> ret; stack<TreeNode*> st; while(!st.empty() || cur) { while(cur) { st.push(cur); ret.push_back(cur->val); cur = cur->left; } TreeNode* top = st.top(); st.pop(); cur = top->right; } return ret; } };
精华在循环中的最后一句代码：cur = top->right;，它让cur的位置从左子树变成了右子树，然后重复之前的步骤。
一个结点出栈，说明这个节点及它的左子树访问完了，就剩右子树。
2. 二叉树的中序遍历
中序遍历的思路也是类似的，不同之处是中序遍历的规则是左子树、根结点、右子树，访问根结点的时机是走完左子树之后，所以是在取出栈顶结点的同时访问根结点的值。
步骤如下：
- 将左路所有结点入栈；
- 取出栈顶结点top的同时访问结点的值，pop。对它的右子树重复步骤1。
- 只要栈或cur至少有一个不为空，则说明还未遍历完毕，继续重复以上操作。
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { TreeNode* cur = root; vector<int> ret; stack<TreeNode*> st; while(!st.empty() || cur) { while(cur) { st.push(cur); cur = cur->left; } TreeNode* top = st.top(); st.pop(); ret.push_back(top->val); cur = top->right; } return ret; } };
3. 二叉树的后序遍历
后序遍历的思路稍有不同，因为后序遍历的规则是先访问完左右子树然后再访问根结点。什么时候能访问结点：
- 左右子树都为空，也就是结点没有孩子；
- 左右子树都访问过；
其实可以不用判断左子树， 因为左子树已经被入栈了，只要看右子树的情况即可。如何判断右子树是否被访问过？
- 用prev保存栈顶结点，那么对于top而言，prev就是上次访问的结点，当
top->right==prev时，表示上一次访问的节点是右子树的根结点，这时候就说明cur的右子树已经被访问过了。
区分：一个结点的右子树不为空的情况下：
- 如果右子树没有访问，应该要访问右子树；
- 右子树访问过了，就要访问根结点。
步骤：
- 将左路所有结点入栈；
- 取栈顶结点top：
- 如果top的右子树已经被访问过了，访问top的值，pop。更新prev为top；
- 如果top的右子树没有被访问，对它的右子树重复步骤1、2。
通过图示理解prev的作用：
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> ret; TreeNode* cur = root; TreeNode* prev = nullptr; // 记录上一次访问的结点 while (cur || !st.empty()) { //1. 将左路结点入栈 while (cur) { st.push(cur); cur = cur->left; } //2. 取出栈顶结点 TreeNode* top = st.top(); //3. 结点的右子树为空，或右子树已经访问过，则访问该结点 if (top->right == nullptr || top->right == prev) { // 访问后弹出 st.pop(); ret.push_back(top->val); // 更新上一次访问的结点 prev = top; } else //4. 若取出结点的右子树还未被访问，访问右子树 { cur = top->right; } } return ret; } };
