Binary Tree Traversal (C++)

之前的版本太多，这里总结一下三种非递归遍历（C++）

preorder

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode *> st;
        TreeNode * p = root;
        while(!st.empty() || p) {
            if(p != NULL) {
                st.push(p);
                result.push_back(p->val);
                p = p->left;
            } else {
                TreeNode * top = st.top();
                st.pop();
                p = top->right;
            }
        }
        return result;
    }
};

inorder

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode *> st;
        TreeNode * p = root;
        while(!st.empty() || p) {
            if(p != NULL) {
                st.push(p);
                p = p->left;
            } else {
                TreeNode * top = st.top();
                st.pop();
                result.push_back(top->val);
                p = top->right;
            }
        }
        return result;
    }
};

postorder

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode *> st;
        TreeNode * p = root;
        TreeNode * pre = NULL;
        while(!st.empty() || p) {
            if(p != NULL) {
                st.push(p);
                p = p->left;
            } else {
                TreeNode * top = st.top();
                if(top->right == NULL || top->right == pre) {
                    st.pop();
                    pre = top;
                    result.push_back(top->val);
                } else {
                    p = top->right;
                }
            }
        }
        return result;
    }
};