如何在一组中打印同一级别的所有节点？

Question

我正在研究 LeetCode 问题 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).

我想打印一组中给定级别的所有节点。我在这个答案 on Stack Overflow.

中找到了执行此操作的方法

但是这个答案使用了递归，而我的代码没有。我想知道我的方法哪里出了问题。

例如给定的输入：[1,2,3,4,null,null,5]

我的输出：[[1],[4],[5]]

预期输出：[[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;
    }
}

Answer 1

您不需要地图、队列或关卡编号。

而是交替使用具有 2 个连续级别的节点的 2 个向量。

另外，按照你的逻辑，addvector最多可以有2个条目，这说明了为什么这种方法行不通。

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

说明

让我们以示例树为例：

parentLevel 从 [1] 开始（实际上 TreeNode 有 1）。

然后外循环开始，内循环将获取 parentLevel 向量中的每个节点并将其值放入 addvector。所以在这次迭代中，addvector 将是 [1].

在同一过程中，这些节点的所有直接 children 都收集在 childLevel 中，因此我们将有节点 [2, 3].

然后内循环结束，addvector 被附加到结果。所以 retvector 将是 [[1]].

现在 children 也会发生同样的情况，因此我们将 childLevel 提升为外循环下一次迭代的 parentLevel。

因此我们开始外循环的下一次迭代，parentLevel 具有 [2, 3]。同样，相应的值被推到一个空的 addvector，然后它将有 [2, 3]。同时 childLevel 填充了 child 个节点 [4, 5].

外循环的第二次迭代将通过将 retvector 扩展到 [[1],[2,3]] 而结束，因此该过程将逐级继续...

如何在一组中打印同一级别的所有节点？

How to print all nodes at the same level in one group?

c++

binary-tree

说明