Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1

    \

     2

    /

   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

分析：

AC代码：

#include<iostream>

#include<vector>

#include<stack>

#include<algorithm>  // 引入 reverse函数，对vector进行反转

using namespace std;

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) {

        vector<int> res(0);

        if(root==NULL) return res;

        stack<TreeNode *> st;

        TreeNode *p=root;

        while(!st.empty()|| p!=NULL)

        {

            if(p!=NULL)

            {

            st.push(p);

            res.push_back(p->val);

            p=p->right;

            }

            if(p==NULL)

            {

                p=st.top();

                p=p->left;

                st.pop();

            }

        }

        reverse(res.begin(),res.end());    // 对向量及其内部结构进行反转

     return res;

    }

};

// 以下为测试

int main()

{

	Solution sol;

	vector<int> res;

	TreeNode *root = new TreeNode(1);

    root->right = new TreeNode(2);

    root->right->left = new TreeNode(3); 

	res=sol.postorderTraversal(root);

	for(int i:res)

		cout<<i<<" ";  // 此处为vector遍历的方法，C++11标准支持

	return 0;

}

另一解法(非递归)：

后序遍历的麻烦在于访问过右子树之后，第二次访问的时候就必须访问根节点，而不是继续访问右子树，所以使用pre来记录上次访问的节点...

class Solution {

public:

    vector<int> postorderTraversal(TreeNode *root) {

        vector<int> ans;

        if(root == NULL) return ans;

        stack<TreeNode* > s;

        TreeNode * p = root;

        TreeNode * pre = NULL;                 //  记录上次访问的节点

        while(p != NULL || !s.empty()) {

            while(p != NULL) {

                s.push(p);

                p = p->left;

            }

            if(!s.empty()) {

                p = s.top();

                s.pop();

                if(p->right == NULL || p->right == pre) {        // 右子树为空，或者是访问过

                    ans.push_back(p->val);

                    pre = p;                         // 记录刚刚访问的右节点

                    p = NULL;

                }

                else {

                    s.push(p);

                    p = p->right;

                }

            }

        }

        return ans;

    }

};