Level-traverse a binary tree

Question

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;
}

Answer 1

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.