Почему этот код для нахождения верхнего вида двоичного дерева неправильный?

`void leftTop(TreeNode<int> *root , vector<int> &topView){
    if(root->left==NULL) return;
    TreeNode<int> *node = root;
    int x=0;
    int xmin=0;
    node = node->left;
    x--;
    while(node){

        if(x<xmin) topView.push_back(node->data);
        xmin=min(xmin,x);
        if(node->left){
            node = node->left;
            x--;
        }
        else if(node->right){
            node = node->right;
            x++;
        } 
        else {
            reverse(topView.begin(),topView.end());
            return;
        }
    }
    reverse(topView.begin(),topView.end());

}
void rightTop(TreeNode<int> *root , vector<int> &topView){
    if(root->right==NULL) return;
    TreeNode<int> *node = root;
    int x=0;
    int xmax=0;
    node = node->right;
    x++;
    while(node){

        if(x>xmax) topView.push_back(node->data);
        xmax=max(xmax,x);
        if(node->right){
            node = node->right;
            x++;
        }
        else if(node->left){
            node = node->left;
            x--;
        }
        else return;
    }

}
vector<int> getTopView(TreeNode<int> *root)
{
   vector<int> topView;
   leftTop(root,topView);
   topView.push_back(root->data);
   rightTop(root,topView);
   return topView;
}

Ответ

Код, представленный для нахождения верхнего вида бинарного дерева, имеет несколько проблем, из-за которых он не работает должным образом. Ниже я объясню основные причины, почему этот код не правильный, и предложу более подходящий способ решения задачи.

Проблемы кода:

1. Неполное отслеживание узлов:
   Код, использующий функции leftTop и rightTop, не учитывает узлы на одном уровне, поскольку он не проверяет, существует ли узел перед его добавлением в результирующий вектор topView. Если узел на одном уровне уже был добавлен (например, при добавлении левого узла), последующий узел (какой-то правый) на том же уровне может не добавиться, что нарушает правильность результата.

2. Логика обхода:
   Логика обхода дерева не охватывает все возможные случаи, когда узлы могут находиться на одной высоте, и допустимо использовать только один, при этом вектор topView может не корректно отображать верхний вид дерева.

3. Отсутствие map или queue:
   Обычно для решения подобных задач используют структуру данных, такую как map, для хранения узлов в соответствии с их горизонтальными координатами. Код, который не использует такие структуры, сложно поддерживать и выводить правильный результат.

Рекомендованное решение:

Вместо использования подхода, представленного в вопросе, вы можете воспользоваться подходом с использованием map и queue. Такой способ гарантирует, что вы охватываете все узлы на одном уровне и сохраняете корректные горизонтальные координаты. Ниже приведен исправленный код:

#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

vector<int> getTopView(TreeNode* root) {
    vector<int> topView;
    if (root == NULL) return topView;

    // Пара (узел, горизонтальная координата)
    map<int, int> topNodes;
    queue<pair<TreeNode*, int>> q;

    // Начинаем с корня (координата 0)
    q.push({root, 0});

    while (!q.empty()) {
        auto current = q.front();
        q.pop();

        TreeNode* node = current.first;
        int hd = current.second; // горизонтальная координата

        // Если еще нет узла на данной координате, добавляем его
        if (topNodes.find(hd) == topNodes.end()) {
            topNodes[hd] = node->data;
        }

        if (node->left) {
            q.push({node->left, hd - 1}); // левая координата на один меньше
        }

        if (node->right) {
            q.push({node->right, hd + 1}); // правая координата на один больше
        }
    }

    // Сортируем по горизонтальным координатам и заполняем вывод
    for (auto& pair : topNodes) {
        topView.push_back(pair.second);
    }

    return topView;
}

Объяснение решения:

1. Мы используем queue для выполнения обхода в ширину (BFS), который позволяет нам обойти дерево по уровням.
2. map используется для отслеживания первого узла, который мы встречаем на каждой горизонтальной координате.
3. После обхода мы просто проходим по map и заполняем результирующий вектор узлов, сохраняя их в порядке горизонтальных координат.

Таким образом, это решение гарантирует, что мы правильно получим верхний вид бинарного дерева.