12 · УПОРЯДОЧЕННОЕ ДЕРЕВО

Бинарное дерево поиска

В BST все значения слева меньше узла, справа — больше; inorder даёт сортировку.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Границы

validate(node, lower, upper)

Передавай допустимый диапазон вниз по дереву.

Inorder

walk(node.Left)
visit(node)
walk(node.Right)

Обход даёт элементы в возрастающем порядке.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Проверка BST

Каждый узел должен лежать в диапазоне предков.

O(n) time · O(height) space

solution.go

func isValidBST(root *TreeNode) bool {
    var valid func(*TreeNode, int64, int64) bool
    valid = func(n *TreeNode, low, high int64) bool {
        if n == nil { return true }
        v := int64(n.Val)
        return low < v && v < high &&
            valid(n.Left, low, v) && valid(n.Right, v, high)
    }
    return valid(root, math.MinInt64, math.MaxInt64)
}

ПРИМЕР РЕШЕНИЯ

K-й минимальный

Inorder посещает значения по возрастанию.

O(height + k) time · O(height) space

solution.go

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    for {
        for root != nil { stack = append(stack, root); root = root.Left }
        root = stack[len(stack)-1]; stack = stack[:len(stack)-1]
        k--
        if k == 0 { return root.Val }
        root = root.Right
    }
}

ПРИМЕР РЕШЕНИЯ

Поиск значения

Свойство BST позволяет на каждом шаге отбросить целое поддерево.

O(height) time · O(1) space

solution.go

func searchBST(root *TreeNode, target int) *TreeNode {
    for root != nil {
        if root.Val == target { return root }
        if target < root.Val { root = root.Left } else { root = root.Right }
    }
    return nil
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Уточни правило для дублей
Не сравнивай только с родителем
Используй int64-границы при int-значениях