145. Binary Tree Postorder Traversal

My intuition is to use stack. But, first time I write the solution, I got TLE for case [1, null, 2]. Then I checked the logic again and find that the problem is in line 23. I notice that the root 1 will be visited twice. When we are done with left child, we’ll visit root once and we goes into right child. And then when we are done with right child, we’ll visit root again. At this time, we don’t want to go visit right child again but pop out the root. So we need to an extra pointer to keep the last node we visited. If the last node is the right child, we know that we are done with visiting children and we need to pop out root.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<int> postorderTraversal(TreeNode* root) {  
13:      vector<int> res;  
14:      stack<TreeNode *> stk;  
15:      TreeNode *cur = root;  
16:      TreeNode *last = NULL;  
17:      while (cur || !stk.empty()) {  
18:        if (cur) {  
19:          stk.push(cur);  
20:          cur = cur->left;  
21:        } else {  
22:          TreeNode *top = stk.top();  
23:          if (top->right && top->right != last) {  
24:            cur = top->right;  
25:          } else {  
26:            res.push_back(top->val);  
27:            last = top;  
28:            stk.pop();  
29:          }  
30:        }  
31:      }  
32:      return res;  
33:    }  
34:  };