В мире конкурентного кодирования LeetCode – популярная платформа, предлагающая широкий спектр задач по программированию. Одной из таких задач является «TreeNode buildTree» (105), которая включает в себя построение двоичного дерева из заданных последовательностей обхода в предварительном и неупорядоченном порядке. В этой записи блога мы рассмотрим различные способы решения этой проблемы, используя простой язык и примеры кода.

Метод 1: рекурсивный подход
Рекурсивный подход — это простой и интуитивно понятный способ решения этой проблемы. Вот краткое описание алгоритма:

1. Определите корень дерева, используя первый элемент из последовательности предварительного заказа.
2. Найдите индекс корневого значения в упорядоченной последовательности.
3. Разбить упорядоченную последовательность на левое и правое поддеревья на основе корневого индекса.
4. Рекурсивно построить левое и правое поддеревья, используя соответствующие части последовательностей предварительного и обратного порядка.
5. Вернуть корневой узел.

class Solution:
    def buildTree(self, preorder, inorder):
        if not preorder or not inorder:
            return None

        root_val = preorder.pop(0)
        root = TreeNode(root_val)
        root_index = inorder.index(root_val)

        root.left = self.buildTree(preorder, inorder[:root_index])
        root.right = self.buildTree(preorder, inorder[root_index+1:])

        return root

Метод 2: оптимизация HashMap
В предыдущем методе мы использовали функцию index()для поиска корневого индекса в упорядоченной последовательности. Однако эта операция имеет временную сложность O(n) в каждом рекурсивном вызове. Мы можем оптимизировать этот процесс, используя HashMap для хранения индексов элементов заказа.

class Solution:
    def buildTree(self, preorder, inorder):
        inorder_map = {val: i for i, val in enumerate(inorder)}

        def helper(pre_start, in_start, in_end):
            if pre_start >= len(preorder) or in_start > in_end:
                return None

            root_val = preorder[pre_start]
            root = TreeNode(root_val)
            root_index = inorder_map[root_val]

            root.left = helper(pre_start+1, in_start, root_index-1)
            root.right = helper(pre_start+root_index-in_start+1, root_index+1, in_end)

            return root

        return helper(0, 0, len(inorder)-1)

В этой статье мы рассмотрели два метода построения двоичного дерева из последовательностей обхода в предварительном и неупорядоченном порядке в задаче LeetCode «TreeNode buildTree» (105). Рекурсивный подход прост и понятен, а оптимизация HashMap обеспечивает более быстрое решение. Освоив эти методы, вы будете хорошо подготовлены к решению аналогичных задач по построению деревьев в LeetCode и улучшите свои навыки программирования.