Binary Tree Postorder Traversal

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

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

return [3,2,1].

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

思路：

用一个栈来保存节点。因为需要记录是否访问了左右子节点，所以用一个pair的第一位来记录当前的访问状态。

代码：

 1     vector<int> postorderTraversal(TreeNode *root) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         vector<int> result;
 5         result.clear();
 6         stack<pair<TreeNode*, int> > treeStack;
 7         if(root == NULL)
 8             return result;
 9         treeStack.push(pair<TreeNode*, int>(root, 0));
10         while(!treeStack.empty()){
11             TreeNode *tNode = treeStack.top().first;
12             int state = treeStack.top().second;
13             treeStack.pop();
14             if(state == 0){
15                 treeStack.push(pair<TreeNode*, int>(tNode, 1));
16                 if(tNode->left){
17                     treeStack.push(pair<TreeNode*, int>(tNode->left, 0));    
18                 }
19             }
20             else if(state == 1){
21                 treeStack.push(pair<TreeNode*, int>(tNode, 2));
22                 if(tNode->right){
23                     treeStack.push(pair<TreeNode*, int>(tNode->right, 0));
24                 }
25             }
26             else{
27                 result.push_back(tNode->val);
28             }
29         }
30         return result;
31     }