c++ - N 元树级别遍历错误 (C++)

Question

我在 LeetCode 上进行编码挑战，我被要求遍历每个级别并在最后返回一个嵌套 vector ，每个值都有值节点值。

所以如果我有这样一棵树:

Which is

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

And expected output is

Output: [[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 叉树，所以我很难理解我的算法哪里出了问题。

Answer 1

您的代码的问题在于，对于您访问的每个节点，您都将其所有子节点作为一个新列表追加到答案列表中。您的代码不会像解决方案所期望的那样将同一级别但具有不同 parent 的 child 分组到一个列表中。

让我们逐步检查您的代码，看看会发生什么:

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

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

• 第一次迭代从堆栈中弹出 1。然后迭代压入堆栈的子项 2、3、4、5。之后，将 child 列表推送到答案列表。

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

• 下一次迭代从堆栈中弹出 5。然后迭代子项 9、10。它们被压入堆栈。之后，将 child 列表推送到答案列表。

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

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

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

• 下一次迭代从堆栈中弹出 9。然后迭代单个 child 13，将其压入堆栈。包含 13 的单例列表被推送到答案集。

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

• 下一次迭代从堆栈中弹出 4。然后迭代单个 child 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;
}

代码使用structured bindings来自 C++17。