来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个二叉树，返回它的 后序 遍历。

例如输入[1,null,2,3] ：

   1
    \
     2
    /
   3 

输出：

[3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

二、题解

参考：二叉树的后序遍历。

三、代码

3.1 通过栈+链表实现

/**
 * 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;
    }
};

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;
    }
};