2
\$\begingroup\$

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.

Full Sample

#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;
}
\$\endgroup\$
  • \$\begingroup\$ first of all it is not broken, it just didn't deal with boundary condition correctly. secondly this code is already written, you can run through the full sample link. \$\endgroup\$ – zinking May 27 '14 at 6:04
2
\$\begingroup\$

I don't see why "DFS" should appear in your code. The challenge is to perform a breadth-first traversal. The typical way to implement a breadth-first traversal is to use a queue.

\$\endgroup\$
  • \$\begingroup\$ you are correct, but I don't see issue implementing this way as well. \$\endgroup\$ – zinking May 27 '14 at 6:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.