Паттерн "сверху вниз"

В паттерне "снизу вверх" мы думали только о том, что вернуть родителю. В паттерне "сверху вниз" добавляется второй вопрос — что передать от родителя ребёнку. То есть теперь нужно думать в обе стороны: что спускаем вниз и что возвращаем наверх.

Суть паттерна "сверху вниз" — при спуске от корня к листьям каждый узел передаёт ребёнку накопленную информацию (например: сумму, глубину, границы, максимум). Благодаря этому в любом узле мы знаем всё, что было выше.

def solve(node, ...):
    if node is None:
        return ...                # базовый случай

    # обновляем переданное значение
    ...

    # рекурсивный спуск с передачей информации детям
    return solve(node.left, ...) or solve(node.right, ...)

Разбор задачи

Дан корень бинарного дерева. Нужно вернуть значения узлов по уровням — сначала все узлы на глубине 0, потом на глубине 1, и так далее.

Ключевая идея решения такая: cпускаемся от корня и несём вниз номер текущего уровня. В каждом узле добавляем его значение в список соответствующего уровня. Если списка для текущего уровня ещё нет — создаём его.

using System.Collections.Generic;

public class Solution
{
    public static List<List<int>> LevelOrderTraversal(TreeNode root)
    {
        List<List<int>> result = new List<List<int>>();
        Preorder(root, 0, result);
        return result;
    }

    private static void Preorder(TreeNode node, int level, List<List<int>> levels)
    {
        if (node == null)
        {
            return;
        }

        // Создаём список для нового уровня
        if (level == levels.Count)
        {
            levels.Add(new List<int>());
        }
        levels[level].Add(node.val);

        Preorder(node.left, level + 1, levels);
        Preorder(node.right, level + 1, levels);
    }
}

#include <vector>

using namespace std;

void preorder(TreeNode* node, int level, vector<vector<int>>& levels) {
    if (node == nullptr) {
        return;
    }

    // создаём список для нового уровня
    if (level == levels.size()) {
        levels.push_back({});
    }
    levels[level].push_back(node->val);

    preorder(node->left, level + 1, levels);
    preorder(node->right, level + 1, levels);
}

vector<vector<int>> levelOrderTraversal(TreeNode* root) {
    vector<vector<int>> result;
    preorder(root, 0, result);
    return result;
}

package main

func levelOrderTraversal(root *TreeNode) [][]int {
    result := [][]int{}

    var preorder func(*TreeNode, int)
    preorder = func(node *TreeNode, level int) {
        if node == nil {
            return
        }

        // создаём список для нового уровня
        if level == len(result) {
            result = append(result, []int{})
        }
        result[level] = append(result[level], node.val)

        preorder(node.left, level+1)
        preorder(node.right, level+1)
    }

    preorder(root, 0)
    return result
}

import java.util.*;

public class Solution {

    public List<List<Integer>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        preorder(root, 0, result);
        return result;
    }

    private void preorder(TreeNode node, int level, List<List<Integer>> levels) {
        if (node == null) {
            return;
        }

        // создаём список для нового уровня
        if (level == levels.size()) {
            levels.add(new ArrayList<>());
        }
        levels.get(level).add(node.val);

        preorder(node.left, level + 1, levels);
        preorder(node.right, level + 1, levels);
    }
}

def preorder(node: TreeNode, level: int, levels: list[list[int]]):
    if node is None:
        return

    # создаём список для нового уровня
    if level == len(levels):
        levels.append([])
    levels[level].append(node.val)

    preorder(node.left, level + 1, levels)
    preorder(node.right, level + 1, levels)


def level_order_traversal(root: TreeNode) -> list[list[int]]:
    result = []
    preorder(root, 0, result)
    return result

/**
 * @param {TreeNode} root
 * @returns {number[][]}
 */
export function levelOrderTraversal(root) {
  const result = [];

  function preorder(node, level) {
    if (node === null) {
      return;
    }

    // создаём список для нового уровня
    if (level === result.length) {
      result.push([]);
    }
    result[level].push(node.val);

    preorder(node.left, level + 1);
    preorder(node.right, level + 1);
  }

  preorder(root, 0);
  return result;
}

Оценка сложности

Время: O(n), где n — число вершин в дереве, в худшем случае обходим все узлы
Память: O(h), где h — высота дерева, память тратится на стек рекурсивных вызовов

Маркеры паттерна "сверху вниз": нужно передавать дополнительную информацию от корня к листьям — сумму, глубину, границы, максимум для формирования ответа.