[leetcode]145-二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode *> s;
        list<TreeNode *> l;
        vector<int> v;
        
        TreeNode *p;
        if (root == nullptr) {
            return v;
        }
        
        s.push(root);
        while (!s.empty()) {
            p = s.top();
            s.pop();
            l.push_front(p);
            if (p->left) {
                s.push(p->left);
            }
            if (p->right) {
                s.push(p->right);
            }
        }
        
        while(!l.empty()) {
            v.push_back(l.front()->val);
            l.pop_front();
        }
        
        return v;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

vector<int> postorderTraversal(TreeNode* root) {

stack<TreeNode *> s;

list<TreeNode *> l;

vector<int> v;

TreeNode *p;

if (root == nullptr) {

return v;

}

s.push(root);

while (!s.empty()) {

p = s.top();

s.pop();

l.push_front(p);

if (p->left) {

s.push(p->left);

}

if (p->right) {

s.push(p->right);

}

while(!l.empty()) {

v.push_back(l.front()->val);

l.pop_front();

}

return v;

}

};

[leetcode]145-二叉树的后序遍历

3.2 通过 2 次压栈实现

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

        return v;
    }
};