Задача: 543. Diameter of Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, вернуть длину диаметра дерева.
Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень.
Длина пути между двумя узлами представлена числом ребер между ними.

Пример:

Input: root = [1,2]
Output: 1

👨‍💻 Алгоритм:

1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS.

2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1.

3⃣Вызвать longestPath с root.

😎 Решение:

class Solution {
    private $diameter;
    
    function diameterOfBinaryTree($root) {
        $this->diameter = 0;
        $this->longestPath($root);
        return $this->diameter;
    }
    
    private function longestPath($node) {
        if ($node === null) return 0;
        
        $leftPath = $this->longestPath($node->left);
        $rightPath = $this->longestPath($node->right);
        
        $this->diameter = max($this->diameter, $leftPath + $rightPath);
        
        return max($leftPath, $rightPath) + 1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний