94. Binary Tree Inorder Traversal

Use stack. If current node is not NULL, then push its left child into the stack. Keep doing this until current node becomes NULL and then pop out the top node from the stack, save the value into result and move to the right child of the popped node.

1:  class Solution {  
2:  public:  
3:    vector<int> inorderTraversal(TreeNode* root) {  
4:      vector<int> res;  
5:      stack<TreeNode *> stk;  
6:      TreeNode *cur = root;  
7:      while (cur || !stk.empty()) {  
8:        if (cur) {  
9:          stk.push(cur);  
10:          cur = cur->left;  
11:        } else {  
12:          TreeNode *p = stk.top();  
13:          res.push_back(p->val);  
14:          stk.pop();  
15:          cur = p->right;  
16:        }  
17:      }  
18:      return res;  
19:    }  
20:  };