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

Question

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

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

---

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

Answer 1

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

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;

}

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

Answer 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 может быть правильным путем.Он естественно подходит для этих поэтапных задач.