Обход бинарного дерева зигзагом в C++

Я пытаюсь предпринять зигзагообразный обход двоичного дерева. Но я застрял в одном типе тестовых случаев, то есть когда дерево не сбалансировано. Если я предоставлю свой вклад как

3
3 9 20 null null 15 7

для двоичного дерева, которое выглядит так:

    3
   / \
  9  20
    /  \
   15   7

Я получаю вывод:

3 
20 9 
0

Если мой ввод был 3 9 20 1 ноль 15 7, мой вывод: 3 20 9 1 0

Ниже мой код.

struct node
    {
        int data;
        node* left;
        node* right;
    };

void order (node* root, map <int, vector <int> >& ans, int level, int k) {
    if (root == NULL) {
        return;
    }

    if (k==0) {
        if (root->left != NULL) {
            ans[level+1].push_back(root->left->data);
            order (root->left, ans, level+1, 1);
        }
        if (root->right != NULL) {
            ans[level+1].push_back(root->right->data);
            order (root->right, ans, level+1, 1);
        }
    }
    else if (k==1) {
        order (root->left, ans, level+1, 0);
        order (root->right, ans, level+1, 0);

        if (root->right != NULL)
            ans[level+1].push_back(root->right->data);
        if (root->left != NULL)
            ans[level+1].push_back(root->left->data);
    }
}

vector<vector<int> > zigzag(node* root){
     map <int, vector <int> > ans;
     vector <vector <int> > zig;

     ans[0].push_back(root->data);

     order(root, ans, 1, 1);

     for (auto it = ans.begin(); it != ans.end(); it++ ) {   //converting map into vector
        zig.push_back(it->second);
     }
     return zig;
 }

Из того, что я понимаю, если ввод нулевой, мой код не должен ничего возвращать и продолжать выполнение других узлов. Я не могу понять свою ошибку. Кто-нибудь может мне помочь? ТИА!

Источник

2 ответа

Решение

Ваш код действительно работает с предоставленным вами тестовым примером. Я подозреваю, что ваша проблема существует с вводом / выводом. Однако само решение, к сожалению, нет. Рассмотрим следующий тестовый пример:

      1
     / \
    5   2
   /     \
  6       3
 /         \
7           4

Ваше решение выведет: [[1], [5, 2], [6, 3], [7, 4]]

Давайте назовем каждый вектор в вашем зигзагообразном векторе уровнем.

  1. Сначала вы добавляете 1 (корень) к своему первому уровню.
  2. k ==1 уровень ==1 Затем вы рекурсивно ушли.
  3. k==0 уровень ==2 Вы правильно добавили 6 к уровню 2. И снова вернулись влево.
  4. k ==1 уровень ==3 Невозможно выполнить рекурсию влево или вправо. Неправильно добавить 7 к уровню 3. Вернуться
  5. k==0 уровень ==2 Невозможно повторить. Вернуть.
  6. k ==1 уровень ==1 Неправильно добавить 5 к уровню 1. Регурсировать правильно.
  7. и т.п.

Я думаю, что этот подход будет трудно найти правильное решение. Прежде всего из-за его природы DFS. Решение BFS может быть правильным путем. Это естественно подходит для этих поэтапных задач.

Источник

Для обхода порядка уровней вы можете использовать структуру данных стека для обхода каждого уровня зигзагообразно.

vector<vector<int> > Solution::zigzagLevelOrder(TreeNode* root) {
    stack<TreeNode*> s1, s2;
    s1.push(root);
    vector< vector< int> > ans;
    int check = 1;
    while(!s1.empty() or !s2.empty()){
        vector<int> current;
        if(check){
            while(!s1.empty()){
                root = s1.top();
                s1.pop();
                current.push_back(root->val);
                if(root->left)
                    s2.push(root->left);
                if(root->right)
                    s2.push(root->right);
            }
            check = 1 - check;
        }
        else{
            while(!s2.empty()){
                root = s2.top();
                s2.pop();
                current.push_back(root->val);
                if(root->right)
                    s1.push(root->right);
                if(root->left)
                    s1.push(root->left);
            }
            check = 1 - check;
        }

        ans.push_back(current);
    }
    return ans;

}

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

Источник
Другие вопросы по тегам