Level traverse binary tree question:
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree
{3,9,20,#,#,15,7}
,3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
The problem is pretty common level order traverse a binary tree but break each level into single array.
I implemented mine: I've designed a few test cases, but when I submit it to the OJ, it just complains about a runtime error. I don't quite understand where the problem is.
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
vector<TreeNode*> headlist;
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > result;
if( root ) {
DFSVisit(root,0);
size_t n=headlist.size();
result.resize(n);
for( size_t i=0; i<n; i++ ){
TreeNode* h = headlist[i];
while( (h ) ){
result[i].push_back( h->val );
h = h->left;
}
reverse( result[i].begin(), result[i].end() );
}
}
return result;
}
void DFSVisit( TreeNode* n, size_t level ){
//cerr << "DFSVISIT" << endl;
TreeNode* l = n->left;
TreeNode* r = n->right;
AppendNodeToHeadlist( n, level );
if( l ) DFSVisit( l, level+1);
if( r ) DFSVisit( r, level+1);
}
void AppendNodeToHeadlist( TreeNode* n, size_t l ){
//cerr << "DFSVISIT" << endl;
//printf( "healist size %lu \n", headlist.size() );
//printf( "node to append %d \n", n->val );
if( headlist.size() < l+1 ){
headlist.push_back(NULL);
headlist[l] = n;
n->left = NULL;
}
else{
TreeNode* h = headlist[l];
h->right = n;
n->left = h;
headlist[l]=n;
//printf( "chain[%lu]: %d->%d\n",l, h->val, n->val );
}
}
};
void print_result( vector<vector<int> >& r ){
//cerr << "DFSVISIT" << endl;
for( size_t i=0; i<r.size(); i++ ){
for( size_t j=0; j<r[i].size(); j++ ){
printf( "%d ", r[i][j] );
}
printf( "\n" );
}
printf( "\n" );
}
void test_solution0(){
Solution s;
auto r = s.levelOrder(NULL);
vector<vector<int> > e;
if ( r == e ){
printf( "CASE0 PASSED!\n" );
}
else{
printf( "CASE0 FAILED!\n" );
printf( "===Actual Result ===\n");
print_result( r );
printf( "===Expected Result ===\n");
print_result( e );
}
}
void test_solution1(){
TreeNode n1(1),n2(2),n3(3),n4(4),n5(5);
n1.left = &n2;
n1.right = &n3;
n3.left = &n4;
n3.right = &n5;
Solution s;
auto r = s.levelOrder(&n1);
vector<vector<int> > e = { {1}, {2,3}, {4,5} };
if ( r == e ){
printf( "CASE1 PASSED!\n" );
}
else{
printf( "CASE1 FAILED!\n" );
printf( "===Actual Result ===\n");
print_result( r );
printf( "===Expected Result ===\n");
print_result( e );
}
}
void test_solution2(){
TreeNode n1(1),n2(2),n3(3),n4(4),n5(5), n6(6);
n1.left = &n2;
n1.right = &n3;
n3.left = &n4;
n3.right = &n5;
n2.left = &n6;
Solution s;
auto r = s.levelOrder(&n1);
vector<vector<int> > e = { {1}, {2,3}, {6,4,5} };
if ( r == e ){
printf( "CASE2 PASSED!\n" );
}
else{
printf( "CASE2 FAILED!\n" );
printf( "===Actual Result ===\n");
print_result( r );
printf( "===Expected Result ===\n");
print_result( e );
}
}
int main(){
test_solution0();
test_solution1();
test_solution2();
return 0;
}
full sample
link. \$\endgroup\$