I am working on the LeetCode problem 102. Binary Tree Level Order Traversal:

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

I want to print all nodes at a given level in one group. I have found a way to do this in this answer on Stack Overflow.

But this answer uses recursion while my code does not. I would like to know where I am going wrong in my approach.

For example given input : [1,2,3,4,null,null,5]

My output : [[1],[4],[5]]

Expected output: [[1],[2,3],[4,5]]

#include <iostream>
#include <vector>
#include <map>
#include <deque>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


vector<vector<int>> levelOrder(TreeNode *root) {
    deque<TreeNode *> queue;
    map<int, vector<int>> myMap;
    vector<vector<int>> retvector;
    vector<int> addvector;
    int level = 0;

    if (root != nullptr) {
        queue.push_back(root);
        addvector.push_back(root->val);
        //retvector.push_back(addvector);
        myMap.insert(pair<int, vector<int>>(level, addvector));
    }

    while (!queue.empty()) {
        TreeNode *ptr = queue.front();
        queue.pop_front();
        addvector.clear();


        if (ptr->left != nullptr) {
            addvector.push_back(ptr->left->val);
            queue.push_back(ptr->left);
        }

        if (ptr->right != nullptr) {
            addvector.push_back(ptr->right->val);
            queue.push_back(ptr->right);
        }

        if (!addvector.empty()) {
            //retvector.push_back(addvector);
            myMap.insert(pair<int, vector<int>>(level, addvector));
            level  ;
            addvector.clear();
        }
    }

    for (int i = 0; i < level; i  ) {
        retvector.push_back(myMap[i]);
    }

    return retvector;
}

int main() {
    TreeNode root, left1, left2, right1, right2;

    left2 = TreeNode(4);
    left1 = TreeNode(2, &left2, nullptr);
    right2 = TreeNode(5);
    right1 = TreeNode(3, nullptr, &right2);
    root = TreeNode(1, &left1, &right1);

    vector<vector<int>> v = levelOrder(&root);

    for (auto &i: v) {
        for (auto &j: i)
            cout << j << " ";
        cout << endl;
    }
}

CodePudding user response：

You don't need a map, nor a queue, nor a level number.

Instead alternate with 2 vectors that have the nodes of 2 consecutive levels.

Also, in your logic, addvector can at the most have 2 entries, which shows why this approach cannot work.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<TreeNode *> parentLevel, childLevel;
        vector<vector<int>> retvector;
        vector<int> addvector;
        
        if (root != nullptr) {
            parentLevel.push_back(root);
        }
        
        while (!parentLevel.empty()) {
            addvector.clear();
            childLevel.clear();
            for (auto parent : parentLevel) {
                addvector.push_back(parent->val);
                if (parent->left != nullptr) {
                    childLevel.push_back(parent->left);
                }
                if (parent->right != nullptr) {
                    childLevel.push_back(parent->right);
                } 
            }
            retvector.push_back(addvector);
            parentLevel = childLevel;
        }

        return retvector;
    }
};

Explanation

Let's take the example tree:

         1
        / \
       2   3
      /     \
     4       5

parentLevel starts out with [1] (actually the TreeNode having 1).

Then the outer loop starts, where the inner loop will take every node in that parentLevel vector and put its value in addvector. So in this iteration, addvector will be [1].

In the same process all direct children of these nodes are collected in childLevel, so there we will have the nodes [2, 3].

The inner loop then finishes, and addvector is appended to the result. So retvector will be [[1]].

Now the same should happen with the children, so we promote childLevel to be the parentLevel for the next iteration of the outer loop.

And so we start the next iteration of the outer loop with parentLevel having [2, 3]. Again, the corresponding values get pushed to an empty addvector, which will then have [2, 3]. At the same time childLevel gets populated with the child nodes [4, 5].

The second iteration of the outer loop will end by extending retvector to [[1],[2,3]], and so the process continues level by level...