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

Метод 1: использование поиска в глубину (DFS)
Один из способов получить представление дерева сверху — выполнить обход поиска в глубину (DFS). Мы можем поддерживать значение горизонтального расстояния для каждого узла, которое представляет горизонтальное положение узла. Обходя дерево рекурсивно и отслеживая горизонтальное расстояние, мы можем сохранить первый узел, встреченный на каждом горизонтальном расстоянии, в хэш-карте. Это даст нам вид дерева сверху.

Вот пример реализации на Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def top_view(root):
    if not root:
        return

    # Dictionary to store the first node at each horizontal distance
    top_view_map = {}

    # Helper function for DFS traversal
    def dfs(node, horizontal_distance, level):
        if node:
            if horizontal_distance not in top_view_map or level < top_view_map[horizontal_distance][1]:
                # Store the current node if it's the first node encountered at this horizontal distance
                top_view_map[horizontal_distance] = (node.val, level)

            # Recursive calls for left and right subtrees
            dfs(node.left, horizontal_distance - 1, level + 1)
            dfs(node.right, horizontal_distance + 1, level + 1)

    # Start DFS traversal from the root
    dfs(root, 0, 0)

    # Extract the top view nodes from the hashmap
    top_view_nodes = [node_val for node_val, _ in sorted(top_view_map.values(), key=lambda x: x[1])]

    return top_view_nodes

Метод 2: использование поиска в ширину (BFS)
Другой подход к получению представления дерева сверху — выполнение обхода поиска в ширину (BFS). Подобно подходу DFS, мы можем поддерживать значение горизонтального расстояния для каждого узла. Однако вместо использования рекурсии мы можем использовать очередь для обхода дерева уровень за уровнем. Отслеживая горизонтальное расстояние и сохраняя первый узел, встреченный на каждом горизонтальном расстоянии, мы можем получить вид дерева сверху.

Вот пример реализации на Java:

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}
public class TreeTopView {
    public List<Integer> topView(TreeNode root) {
        List<Integer> topViewNodes = new ArrayList<>();
        if (root == null)
            return topViewNodes;

        // Map to store the first node at each horizontal distance
        Map<Integer, Integer> topViewMap = new HashMap<>();

        // Queue for BFS traversal
        Queue<QueueNode> queue = new LinkedList<>();
        queue.offer(new QueueNode(root, 0));

        while (!queue.isEmpty()) {
            QueueNode node = queue.poll();
            int horizontalDistance = node.horizontalDistance;

            // Store the first node encountered at this horizontal distance
            if (!topViewMap.containsKey(horizontalDistance))
                topViewMap.put(horizontalDistance, node.treeNode.val);

            if (node.treeNode.left != null)
                queue.offer(new QueueNode(node.treeNode.left, horizontalDistance - 1));

            if (node.treeNode.right != null)
                queue.offer(new QueueNode(node.treeNode.right, horizontalDistance + 1));
        }
// Extract the top view nodes from the map
        topViewNodes.addAll(topViewMap.values());

        return topViewNodes;
    }

    static class QueueNode {
        TreeNode treeNode;
        int horizontalDistance;

        QueueNode(TreeNode treeNode, int horizontalDistance) {
            this.treeNode = treeNode;
            this.horizontalDistance = horizontalDistance;
        }
    }
}

В этой статье мы рассмотрели два метода получения вида сверху дерева: один с использованием поиска в глубину (DFS), а другой с использованием поиска в ширину (BFS). Оба метода позволяют визуализировать узлы дерева, если смотреть сверху. Реализуя эти методы на предпочитаемом вами языке программирования, вы можете легко извлечь вид дерева сверху и использовать его для различных приложений.

Не забудьте выбрать метод, который соответствует вашим конкретным требованиям, исходя из таких факторов, как эффективность и использование памяти. Приятного кодирования!