binary tree inorder travelsal

binary tree inorder travelsal

Easy problem too

Recursive way is easy, and iterative way is also not hard. Using a stack and just save the path. visited root, DFS left, come back to root, push root to the result, DFS right.

Recursive way

 1 /**
 2  * Definition for binary tree
 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         vector < int > result;
14         result.clear();
15         inOrder(root,result);
16         return result;
17     }
18     void inOrder( TreeNode* root, vector < int > &result ) {
19         if ( !root ) {
20             return;
21         }
22         inOrder(root->left,result);
23         result.push_back(root->val);
24         inOrder(root->right,result);
25     }
26 };

Iterative way

 1 /**
 2  * Definition for binary tree
 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         vector < int > result;
14         result.clear();
15         if ( !root ) {
16             return result;
17         }
18         stack < pair< TreeNode*, int > > S;
19         while( !S.empty() ) {
20             S.pop();
21         }
22         S.push( pair < TreeNode*, int > (root,0) );
23         while ( !S.empty() ) {
24             auto p = S.top();
25             S.pop();
26             if ( p.second == 1 ) {
27                 result.push_back(p.first->val);
28             } else {
29                 if ( p.first->right ) {
30                     S.push(pair < TreeNode*, int > (p.first->right,0));
31                 }
32                 S.push(pair < TreeNode*, int > (p.first,1));
33                 if ( p.first->left ) {
34                     S.push(pair < TreeNode*, int > (p.first->left,0));
35                 }
36             }
37         }
38         return result;
39     }
40 };

Loading Disqus comments...
Table of Contents