Усложнение паттерна "снизу вверх"

Раньше в задачах выше ответ совпадал с тем, что мы возвращали родителю. Но так бывает не всегда — иногда ответ задачи и возвращаемое значение это разные вещи по смыслу.

Простой случай — высота дерева

Высота дерева — число узлов в самой длинной ветке. Здесь всё просто: возвращаем максимум из левого и правого + 1. Ответ задачи = возвращаемое значение.

def max_depth(node):
    if node is None:
        return 0

    left  = max_depth(node.left)
    right = max_depth(node.right)

    return max(left, right) + 1

Усложнение — диаметр дерева

Дан корень бинарного дерева. Нужно найти диаметр — длину самого длинного пути (в рёбрах) между любыми двумя узлами. Путь не обязательно проходит через корень.

Диаметр через узел = высота левого поддерева + высота правого поддерева. Но родителю мы возвращаем не диаметр, а высоту — ответ и возвращаемое значение разные по смыслу. Поэтому диаметр обновляется отдельно через замыкание, а наверх идёт только высота.

public class Solution
{
    private static int diameter;

    public static int FindDiameter(TreeNode root)
    {
        diameter = 0;
        Dfs(root);
        return diameter;
    }

    private static int Dfs(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }

        int left = Dfs(node.left);
        int right = Dfs(node.right);

        // Обновляем максимальный диаметр
        diameter = Math.Max(diameter, left + right);

        return Math.Max(left, right) + 1;
    }
}

#include <algorithm>

using namespace std;

int dfs(TreeNode* node, int& diameter) {
    if (node == nullptr) {
        return 0;
    }

    int left = dfs(node->left, diameter);
    int right = dfs(node->right, diameter);

    // обновляем максимальный диаметр
    diameter = max(diameter, left + right);

    return max(left, right) + 1;
}

int findDiameter(TreeNode* root) {
    int diameter = 0;
    dfs(root, diameter);
    return diameter;
}

package main

func findDiameter(root *TreeNode) int {
    diameter := 0

    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        left := dfs(node.left)
        right := dfs(node.right)

        // обновляем максимальный диаметр
        diameter = max(diameter, left+right)

        return max(left, right) + 1
    }

    dfs(root)
    return diameter
}

public class Solution {

    private int diameter = 0;

    public int findDiameter(TreeNode root) {
        dfs(root);
        return diameter;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = dfs(node.left);
        int right = dfs(node.right);

        // обновляем максимальный диаметр
        diameter = Math.max(diameter, left + right);

        return Math.max(left, right) + 1;
    }
}

from typing import *


def find_diameter(root: Optional[TreeNode]) -> int:
    diameter = 0

    def dfs(node: Optional[TreeNode]) -> int:
        nonlocal diameter
        if node is None:
            return 0

        left = dfs(node.left)
        right = dfs(node.right)

        # обновляем максимальный диаметр
        diameter = max(diameter, left + right)

        return max(left, right) + 1

    dfs(root)
    return diameter

/**
 * @param {TreeNode} root
 * @returns {number}
 */
export function findDiameter(root) {
  let diameter = 0;

  function dfs(node) {
    if (node === null) {
      return 0;
    }

    const left = dfs(node.left);
    const right = dfs(node.right);

    // обновляем максимальный диаметр
    diameter = Math.max(diameter, left + right);

    return Math.max(left, right) + 1;
  }

  dfs(root);
  return diameter;
}

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

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

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