94. Binary Tree Inorder Traversal

The idea is to keep pushing left child nodes into the stack. And pop out the top one, move the pointer to its right and then keep pushing left child nodes again.

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> inorderTraversal(TreeNode* root) {  
13:      stack<TreeNode*> stk;  
14:      TreeNode *p = root;  
15:      vector<int> res;  
16:      while (p || !stk.empty()) {  
17:        while (p) {  
18:          stk.push(p);  
19:          p = p->left;  
20:        }  
21:        p = stk.top();  
22:        stk.pop();  
23:        res.push_back(p->val);  
24:        p = p->right;  
25:      }  
26:      return res;  
27:    }  
28:  };