N叉树层序遍历问题 (C++)

Question

我正在参加LeetCode的编程挑战，要求我遍历每个节点，并在最后返回一个嵌套向量，其中包含每层的节点值。

例如，如果我有如下树：

这是

输入: root = [1,null,3,2,4,null,5,6]

期望输出为

输出: [[1],[3,2,4],[5,6]]

节点的定义如下:

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

我正在尝试一种迭代解决方案，具体如下：

class Solution {
public:
    vector<vector<int>> answer;
    stack<Node*> nodes;
    vector<vector<int>> levelOrder(Node* root) {
        if(root == NULL)
            return answer;
        nodes.push(root);
        answer.push_back(vector<int>() = {root->val});
        while(!nodes.empty())
        {
            Node* curr = nodes.top();
            nodes.pop();
            vector<int>temp;

            for(int i = 0; i < curr->children.size(); i++)
            {
                nodes.push(curr->children[i]);
                temp.push_back(curr->children[i]->val);
            }
            if(temp.size() != 0)
                answer.push_back(temp);
        }
        return answer;
    }
};

然而，它在第20个测试用例中始终失败，该输入为：

[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

期望是：

[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

我的输出是

[[1],[2,3,4,5],[9,10],[13],[8],[12],[6,7],[11],[14]]

我在纸上无法准确地展现和绘制这个N叉树，因此很难理解我的算法出了什么问题。

- Vocaloidas

---

如果你仔细看一下你引用的示例输入和输出，你会发现你根本不需要构建任何树。输出只是与输入中相同的一系列数据，只是用[]分组而不是用,和null分隔。但是，你需要计算属于每个级别的运行次数。例如，如果节点4有一个子节点8，输入将看起来像[1,null,3,2,4,null,5,6,null,null,8]，期望的输出将是[[1],[3,2,4],[5,6,8]] - 注意在树的第三行中三个运行（一个为空）的连接。 - CiaPan

Answer 1

你的代码问题在于，对于每个访问的节点，你将其所有子节点作为一个新列表附加到答案列表中。你的代码没有将同一级别但具有不同父节点的子节点分组到一个列表中，这是解决方案所期望的。

让我们逐步了解你的代码发生了什么：

• 在循环之前，您将根节点推入堆栈，并将具有根节点值的单例集合推入答案：

  stack = {1}
  answer = { {1} }
  

• 第一次迭代从堆栈中弹出1。然后，您遍历子节点2、3、4、5，并将它们推入堆栈。之后，子节点列表被推入答案列表。

  stack = {2,3,4,5}
  answer = { {1}, {2,3,4,5} }
  

下一次迭代从堆栈中弹出5。然后您遍历子节点9、10。它们被推入堆栈。之后，将子节点列表推入答案列表。

stack = {2,3,4,9,10}
answer = { {1}, {2,3,4,5}, {9, 10} }

下一次迭代从堆栈中弹出10。它没有子节点，所以什么也不会发生。

stack = {2,3,4,9}
answer = { {1}, {2,3,4,5}, {9, 10} }

下一次迭代从堆栈中弹出9。然后您遍历单个子节点13，将其推入堆栈。将包含13的单例列表推入答案集。

stack = {2,3,4}
answer = { {1}, {2,3,4,5}, {9, 10}, {13} }

下一次迭代从堆栈中弹出4。然后您遍历单个子节点8，将其推入堆栈。将包含8的单例列表推入答案集。

stack = {2,3,8}
answer = { {1}, {2,3,4,5}, {9, 10}, {13}, {8} }

您可以从这里看到您的答案列表是错误的。8与9和10处于同一级别，因此它应该被添加到答案列表中的{9,10}子列表中，而不是创建一个新列表{8}。这应该足以说明问题，因此我将不再进一步解释代码。

为了确保同一层级的节点被分组到答案列表的同一个子列表中，我们在访问每个节点时必须跟踪当前层级。我们可以通过扩展堆栈来保存当前节点和其深度的对，从而实现这一点。然后，深度为d的每个节点值将附加到答案列表中的第d个子列表中。这确保了同一层级的节点被分组到一个子列表中。

std::vector<std::vector<int>> get_vals_per_level(const Node *root) {

  std::vector<std::vector<int>> vals_per_level{};
  std::stack<std::pair<const Node *, int>> stack{};

  stack.emplace(root, 0);

  while (!stack.empty()) {
    auto [current, depth]{stack.top()};
    stack.pop();

    if (vals_per_level.size() == depth) {
      vals_per_level.emplace_back();
    }

    // Append node value to the answer list for the current depth
    vals_per_level[depth].push_back(current->val);

    auto& children{current->children};

    for (auto it{children.rbegin()}; it != children.rend(); it++) {
      stack.emplace(*it, depth + 1);
    }
  }

  return vals_per_level;
}

这段代码使用了 C++17 中的 结构化绑定。

- f9c69e9781fa194211448473495534