Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree
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
» Solve this problem"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.[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: }
No comments:
Post a Comment