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?

C++:
01 vector<int> inorderTraversal(TreeNode *root) {
02         stack <TreeNode*> S;
03         vector <int> V;
04         if(root==NULL)
05             return V;
06         S.push(root);
07         TreeNode* prv=NULL;
08         while(!S.empty()){
09             TreeNode* tmp=S.top();
10             S.pop();
11             if((prv==NULL)||(prv->left==tmp)||(prv->right==tmp)){
12                 if(tmp->right)
13                     S.push(tmp->right);
14                 S.push(tmp);
15                 if(tmp->left)
16                     S.push(tmp->left);
17                 prv=tmp;
18                 continue;
19             }
20             V.push_back(tmp->val);
21             prv=tmp;
22         }
23 }
Advertisements
This entry was posted in Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s