11 · ИЕРАРХИЯ

Бинарные деревья

Рекурсивная функция обычно возвращает информацию о поддереве родителю.

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

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

Примитивы Go

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

Узел

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

Базовый случай рекурсии — node == nil.

DFS

var dfs func(*TreeNode) int
dfs = func(node *TreeNode) int { /* ... */ }

Замыкание удобно, если нужен внешний ответ.

ПРАКТИКА

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

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

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

Максимальная глубина

Глубина = 1 + максимум глубин детей.

O(n) time · O(height) space

solution.go

func maxDepth(root *TreeNode) int {
    if root == nil { return 0 }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

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

Максимальная сумма пути

Родителю отдаём только одну лучшую ветвь.

O(n) time · O(height) space

solution.go

func maxPathSum(root *TreeNode) int {
    best := math.MinInt
    var gain func(*TreeNode) int
    gain = func(node *TreeNode) int {
        if node == nil { return 0 }
        left, right := max(0, gain(node.Left)), max(0, gain(node.Right))
        best = max(best, node.Val+left+right)
        return node.Val + max(left, right)
    }
    gain(root)
    return best
}

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

Инвертирование дерева

Меняем детей местами и рекурсивно обрабатываем оба поддерева.

O(n) time · O(height) space

solution.go

func invertTree(root *TreeNode) *TreeNode {
    if root == nil { return nil }
    root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
    return root
}

ПЕРЕД КОДОМ

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

Что возвращает вызов для поддерева
Preorder, inorder или postorder
Оцени высоту рекурсивного стека