One of C++ solutions (preorder)


  • 102
    N
    vector<vector<int>> ret;
    
    void buildVector(TreeNode *root, int depth)
    {
        if(root == NULL) return;
        if(ret.size() == depth)
            ret.push_back(vector<int>());
        
        ret[depth].push_back(root->val);
        buildVector(root->left, depth + 1);
        buildVector(root->right, depth + 1);
    }
    
    vector<vector<int> > levelOrder(TreeNode *root) {
        buildVector(root, 0);
        return ret;
    }

  • 2
    T

    i wonder what's this means? ret.push_back(vector<int>( ) );


  • 1
    S

    Great solution! Doesn't use extra space for a queue like other implementations. Also funny how the problem is called Level Order Traversal, but you used preorder and it still worked. Really thinking outside the box there.


  • 1
    J

    Nice. But call stack of recursive method should be considered as extra space, too.


  • 10
    Q

    there are tradeoffs,
    for very 'lean' tree (most non-leaf node have only one child), this dfs appoach consume O(n) memory, while bfs approach with queue cost almost constant space.
    for near complete tree (most non-leaf node have two child), dfs approach cost O(log(n)) memory, whereas bfs approach cost O(n) memory


  • 0
    Z

    good solution!


  • 1
    Y

    It is the initialization of each level


  • 1
    F

    I'm also a little bit confused about this


  • 0
    A

    nice job about comparing ret size with depth. I was also thinking using recursion, but gave up to iteration


  • 0
    P

    Brilliant!! However, sometimes really don't know how to design the recursion solution...


  • 0

    Nice solution, I really like this part: if(ret.size() == depth)


  • 0
    W

    Thank you for your comment


  • 0
    H

    Very nice code. But why it is wrong if I change

    if(ret.size() == depth)
            ret.push_back(vector<int>());
    

    to

    if(depth > ret.size() - 1)
            ret.push_back(vector<int>());
    

  • 2
    V

    @haoranc this has something to do with the subtraction of unsigned int and signed int. Change it to
    if(depth>(int)(ret.size()-1)) should solve the problem


  • 0
    V

    @nilath Cool, I had the same idea . it's sort of dfs , although the exercise itself points very much to the direction of bfs.


  • 1
    S

    @tyk This means constructing an empty vector as the d-th(depth) element of the 2-d vector ret.


  • 0
    T

    vector<int>();mean:
    0_1481026166409_upload-eb91029b-316f-4414-86d8-42a429d26266


  • 0
    M

    Why do we have to use initialize the returning vector globally? Tried returning the vector recursively and it didn't work.


  • 0
    D

    @mithun96 If you don't want to use global variable, you can put the vector inside the function as a parameter:

        void buildVector(TreeNode *root, int depth,vector<vector<int>> & ret)
        {
            if(root == NULL) return;
            if(ret.size() == depth)
                ret.push_back(vector<int>());
            
            ret[depth].push_back(root->val);
            buildVector(root->left, depth + 1, ret);
            buildVector(root->right, depth + 1, ret);
        }
        
        vector<vector<int> > levelOrder(TreeNode *root) {
            vector<vector<int>> ret;
            buildVector(root, 0, ret);
            return ret;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.