N-арная ошибка обхода уровня дерева (C ++) - PullRequest
Новая
       42

N-арная ошибка обхода уровня дерева (C ++)

1 голос
/ 05 января 2020

Я делаю вызов кодирования в LeetCode, и меня просят пройти каждый уровень и в конце вернуть вложенные векторы со значениями узлов значений для каждого значения.

Так что, если у меня есть дерево, подобное :

enter image description here

Что составляет

Ввод: root = [1, ноль, 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-арного дерева на бумаге, поэтому мне трудно понять, где мой алгоритм пошел не так, как надо.

...