[LeetCode] Binary Tree Inorder Traversal Solution

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

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

   1
    \
     2
    /
   3

return [1,3,2].

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem

[Thoughts]
For recursion version, it's very easy to write.

But for iterative version, we need a stack to help.


[Code]
Recursion version

1:    vector<int> inorderTraversal(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<int> result;  
5:      inorderTra(root, result);  
6:      return result;  
7:    }  
8:    void inorderTra(TreeNode* node, vector<int> &result)  
9:    {  
10:      if(node == NULL)  
11:      {        
12:        return;  
13:      }  
14:      inorderTra(node->left, result);  
15:      result.push_back(node->val);      
16:      inorderTra(node->right, result);  
17:    }  

Iteration version

1:    vector<int> inorderTraversal(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<TreeNode*> sta;  
5:      vector<int> result;  
6:      if(root == NULL) return result;  
7:      TreeNode* node =root;  
8:      while(sta.size()>0 || node!=NULL)  
9:      {  
10:        while(node!=NULL)  
11:        {  
12:          sta.push_back(node);  
13:          node = node->left;  
14:        }  
15:        node= sta.back();  
16:        sta.pop_back();  
17:        result.push_back(node->val);  
18:        node =node->right;  
19:      }  
20:      return result;  
21:    }