binary tree level order travelsal I II

binary tree level order travelsal I II

I Not hard

Mind if root is NULL!

 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<vector<int> > levelOrder(TreeNode *root) {
13         vector< vector < int > > result;
14         result.clear();
15         if ( !root ) {
16             return result;
17         }
18         queue < pair < TreeNode*, int > > Q;
19         while ( !Q.empty() ) {
20             Q.pop();
21         }
22         Q.push(pair < TreeNode*, int >(root,0));
23         vector< int > t;
24         t.clear();
25         while( !Q.empty() ) {
26             auto p = Q.front();
27             Q.pop();
28             t.push_back(p.first->val);
29             if ( Q.empty() || p.second != Q.front().second ) {
30                 result.push_back(t);
31                 t.clear();
32             }
33             if ( p.first->left ) {
34                 Q.push(pair < TreeNode*, int >(p.first->left,p.second+1));
35             }
36             if ( p.first->right ) {
37                 Q.push(pair < TreeNode*, int >(p.first->right,p.second+1));
38             }
39         }
40         return result;
41     }
42 };

II not hard too

Use stack first then put them into vector.

 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<vector<int> > levelOrderBottom(TreeNode *root) {
13         stack < vector < int > > S;
14         while ( !S.empty() ) {
15             S.pop();
16         } 
17         vector < vector < int > > result;
18         result.clear();
19         if ( !root ) {
20             return result;
21         }
22         queue < pair < TreeNode*, int > > Q;
23         while ( !Q.empty() ) {
24             Q.pop();
25         }
26         Q.push(pair < TreeNode*, int >(root,0));
27         vector < int > t;
28         t.clear();
29         while ( !Q.empty() ) {
30             auto p = Q.front();
31             Q.pop();
32             t.push_back(p.first->val);
33             if ( Q.empty() || p.second != Q.front().second ) {
34                 S.push(t);
35                 t.clear();
36             }
37             if ( p.first->left ) {
38                 Q.push(pair< TreeNode*, int>(p.first->left,p.second+1));
39             }
40             if ( p.first->right ) {
41                 Q.push(pair< TreeNode*, int>(p.first->right,p.second+1));
42             }
43         }
44         while ( !S.empty() ) {
45             result.push_back(S.top());
46             S.pop();
47         }
48         return result;
49     }
50 };

II using reverse

Put the result in vector, after BFS, reverse it.

 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<vector<int> > levelOrderBottom(TreeNode *root) {
13         vector < vector < int > > result;
14         result.clear();
15         if ( !root ) {
16             return result;
17         }
18         queue < pair < TreeNode*, int > > Q;
19         while ( !Q.empty() ) {
20             Q.pop();
21         }
22         Q.push(pair < TreeNode*, int >(root,0));
23         vector < int > t;
24         t.clear();
25         while ( !Q.empty() ) {
26             auto p = Q.front();
27             Q.pop();
28             t.push_back(p.first->val);
29             if ( Q.empty() || p.second != Q.front().second ) {
30                 result.push_back(t);
31                 t.clear();
32             }
33             if ( p.first->left ) {
34                 Q.push(pair< TreeNode*, int>(p.first->left,p.second+1));
35             }
36             if ( p.first->right ) {
37                 Q.push(pair< TreeNode*, int>(p.first->right,p.second+1));
38             }
39         }
40         reverse(result.begin(),result.end());
41         return result;
42     }
43 };

Loading Disqus comments...
Table of Contents