fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7.  
  8. struct TreeNode {
  9.     int val;
  10.     TreeNode *left;
  11.     TreeNode *right;
  12.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  13. };
  14.  
  15. // class Tree2Link {
  16. // public:
  17.     // TreeNode* ConvertTree2Link( TreeNode* n ){
  18.     // }
  19.  
  20.     // void VisitTreeNode( TreeNode* n , int level, TreeNode** ph ){
  21.     //    TreeNode* h = *ph;
  22.  
  23.  
  24.     // }
  25.  
  26.     // void LinkWithHead(  TreeNode** ph, TreeNode* c ){
  27.         // if( !c ) return;
  28.         // TreeNode* h = *ph;
  29.         // h->left = c;
  30.         // c->right = h;
  31.         // *ph = c;
  32.     // }
  33. // };
  34.  
  35. class Solution {
  36.     vector<TreeNode*> headlist;
  37. public:
  38.     vector<vector<int> > levelOrder(TreeNode *root) {
  39.     	vector<vector<int> > result;
  40.         if( root ) {
  41.         	DFSVisit(root,0);
  42. 	        size_t n=headlist.size();
  43. 	        result.resize(n);
  44. 	        for( size_t i=0; i<n; i++ ){
  45. 	            TreeNode* h = headlist[i];
  46. 	            while( (h ) ){
  47. 	                result[i].push_back( h->val );
  48. 	                h = h->left;
  49. 	            }
  50. 	            reverse( result[i].begin(), result[i].end() );
  51. 	        }
  52.         }
  53.         return result;
  54.  
  55.     }
  56.  
  57.     void DFSVisit( TreeNode* n, size_t level ){
  58.     	//cerr << "DFSVISIT" << endl;
  59.         TreeNode* l = n->left;
  60.         TreeNode* r = n->right;
  61.         AppendNodeToHeadlist( n, level );
  62.         if( l  ) DFSVisit( l, level+1);
  63.         if( r  ) DFSVisit( r, level+1);
  64.     }
  65.  
  66.     void AppendNodeToHeadlist( TreeNode* n, size_t l ){
  67.     	//cerr << "DFSVISIT" << endl;
  68.         //printf( "healist size %lu \n", headlist.size() );
  69.         //printf( "node to append %d \n", n->val );
  70.         if( headlist.size() < l+1 ){
  71.             headlist.push_back(NULL);
  72.             headlist[l] = n;
  73.             n->left = NULL;
  74.         }
  75.         else{
  76.             //printf( "setting head of %lu from %d to %d\n", l, headlist[l]->val, n->val );
  77.             TreeNode* h = headlist[l];
  78.             h->right = n;
  79.             n->left  = h;
  80.             headlist[l]=n;
  81.             //printf( "chain[%lu]: %d->%d\n",l, h->val, n->val );
  82.  
  83.         }
  84.     }
  85. };
  86.  
  87. void print_result( vector<vector<int> >& r ){
  88.     //cerr << "DFSVISIT" << endl;
  89.     for( size_t i=0; i<r.size(); i++ ){
  90.         for( size_t j=0; j<r[i].size(); j++ ){
  91.             printf( "%d ", r[i][j] );
  92.         }
  93.         printf( "\n" );
  94.     }
  95.     printf( "\n" );
  96. }
  97.  
  98. void test_solution0(){
  99.  
  100.     Solution s;
  101.     auto r = s.levelOrder(NULL);
  102.     vector<vector<int> > e;
  103.     if ( r == e ){
  104.         printf( "CASE0 PASSED!\n" );
  105.     }
  106.     else{
  107.         printf( "CASE0 FAILED!\n" );
  108.         printf( "===Actual   Result ===\n");
  109.         print_result( r );
  110.         printf( "===Expected Result ===\n");
  111.         print_result( e );
  112.     }
  113.  
  114. }
  115.  
  116. void test_solution1(){
  117.     TreeNode n1(1),n2(2),n3(3),n4(4),n5(5);
  118.     n1.left  = &n2;
  119.     n1.right = &n3;
  120.     n3.left  = &n4;
  121.     n3.right = &n5;
  122.  
  123.     Solution s;
  124.     auto r = s.levelOrder(&n1);
  125.     vector<vector<int> > e = { {1}, {2,3}, {4,5} };
  126.     if ( r == e ){
  127.         printf( "CASE1 PASSED!\n" );
  128.     }
  129.     else{
  130.         printf( "CASE1 FAILED!\n" );
  131.         printf( "===Actual   Result ===\n");
  132.         print_result( r );
  133.         printf( "===Expected Result ===\n");
  134.         print_result( e );
  135.     }
  136.  
  137. }
  138.  
  139. void test_solution2(){
  140.     TreeNode n1(1),n2(2),n3(3),n4(4),n5(5), n6(6);
  141.     n1.left  = &n2;
  142.     n1.right = &n3;
  143.     n3.left  = &n4;
  144.     n3.right = &n5;
  145.     n2.left  = &n6;
  146.  
  147.     Solution s;
  148.     auto r = s.levelOrder(&n1);
  149.     vector<vector<int> > e = { {1}, {2,3}, {6,4,5} };
  150.     if ( r == e ){
  151.         printf( "CASE2 PASSED!\n" );
  152.     }
  153.     else{
  154.         printf( "CASE2 FAILED!\n" );
  155.         printf( "===Actual   Result ===\n");
  156.         print_result( r );
  157.         printf( "===Expected Result ===\n");
  158.         print_result( e );
  159.     }
  160.  
  161. }
  162.  
  163. int main(){
  164. 	test_solution0();
  165. 	test_solution1();
  166. 	test_solution2();
  167.     return 0;
  168. }
  169.  
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
CASE0 PASSED!
CASE1 PASSED!
CASE2 PASSED!
https://ideone.com/heL0Jj
http://o...content-available-to-author-only...e.com/problems/binary-tree-level-order-traversal/
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!