C++二元樹的前序中序後序非遞迴實現方法詳細講解

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        while(!st.empty()||cur)
        {
            //左路節點
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }
            //左路節點右子樹
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;//轉化成子問題存取右子樹
        }
        return v;
    }
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        while(cur||!st.empty())
        {
            while(cur)
            {
                //不存取
                st.push(cur);
                cur = cur->left;
            }
            TreeNode*top = st.top();
            //進行存取
            v.push_back(top->val);
            st.pop();
            cur = top->right;
        }
        return v;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        TreeNode*prev = nullptr;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode*top = st.top();
            //top的右子樹為空，或者右子樹已經存取過了（上一個存取節點時右子樹的根）那麼說明右子樹不用存取或者存取過了，可以存取根top
            //右子樹不為空，且沒有存取， 則迭代子問題存取
            if(top->right==nullptr||top->right==prev)
            {
                st.pop();
                v.push_back(top->val);
                prev = top;
            }
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};