## Monday, November 10, 2014

### [LeetCode] Binary Tree Inorder Traversal

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?

1. 递归解法：

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15``` ```class Solution { public: vector inorderTraversal(TreeNode *root) { vector allNodeValues; inorderTrav(root, allNodeValues); return allNodeValues; } void inorderTrav(TreeNode *root, vector &allNodeValues) { if(!root) return; inorderTrav(root->left, allNodeValues); allNodeValues.push_back(root->val); inorderTrav(root->right, allNodeValues); } }; ```

2. 迭代解法：

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

#### 1 comment:

1. Can you provide this solution in C.