[leetcode] 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].

给定一棵二叉树，使用非递归的方法返回后序遍历结果。后序遍历需要先访问左子树，然后再访问右子树，最后访问自己。因此需要记录该节点的左右子树是否已经全部访问，如果访问完毕，那么就可以访问自己了。

代码如下：

 1 class Solution {
 2 public:
 3     vector<int> postorderTraversal(TreeNode *root) {
 4         // IMPORTANT: Please reset any member data you declared, as
 5         // the same Solution instance will be reused for each test case.
 6         vector<int> ans;
 7         list<TreeNode*> node_list;
 8         if(root == NULL) return ans;
 9         node_list.push_front(root);
10         TreeNode *head = root;
11         while(!node_list.empty())
12         {
13             TreeNode *cur = node_list.front();
14             if(cur -> right == head || cur -> left == head || ((cur -> right == NULL) && (cur -> left == NULL)))
15             {
16                 node_list.pop_front();
17                 ans.push_back(cur -> val);
18                 head = cur;
19             }
20             else
21             {
22                 if(cur -> right != NULL) node_list.push_front(cur -> right);
23                 if(cur -> left != NULL) node_list.push_front(cur -> left);
24             }
25         }
26     }
27 };