非递归的思路。

个人感觉这句话很有用。

本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈。

中序遍历

左中右，在递归的时候，如果当前节点有左子树，我们就递归左子树，然后输出中间节点，然后递归右子树。
我们用stack模拟这个操作。

 vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        stack<TreeNode *> st;
        TreeNode* cur = root;

        vector<int>ans;
        while(!st.empty() || !cur){
            while(cur){
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* now  = st.top();st.pop();
            ans.push_back(now->val);
            if(now->right){
                cur = now->right;
            }
        }
        return ans;

    }

前序遍历

根左右。

    vector<int> preorderTraversal(TreeNode* root) {

        // 迭代版。用stack，
        // vector<int>ans;
        // stack<TreeNode*>st;
        // if(root!= NULL) st.push(root);
        // while(!st.empty()){
        //     TreeNode* top = st.top();st.pop();
        //     ans.push_back(top->val);
        //     if(top->right) st.push(top->right);
        //     if(top->left) st.push(top->left);
        // }
         vector<int>ans;
         stack<TreeNode*>st;
         TreeNode* cur = root;
         while(!st.empty() || cur){
             while(cur){
                 ans.push_back(cur->val);
                 st.push(cur);
                 cur=cur->left;
             }
             TreeNode* now = st.top();st.pop();
             if(now->right){
                 cur = now->right;
             }
         }

        return ans;
    }

后序遍历

后序遍历由前序遍历更改而来。 前序遍历是 根左右。 后序遍历是 左右根 = reverse(根右左)。

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>ans;
        TreeNode* cur = root;
        //后序遍历由前序遍历更改而来。 前序遍历是 根左右。 后序遍历是 左右根 = reverse(根右左)。
        stack<TreeNode*> st;
        while(!st.empty() || cur){
            while(cur){
                ans.push_back(cur->val);
                st.push(cur);
                cur = cur->right; // 先右
            }
            TreeNode* now = st.top();st.pop();
            if (now->left) cur = now->left; // 后左
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }

参考链接

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-hou-xu-fei-di-gui-bian-li-liang-chong-z/