Задача: 687. Longest Univalue Path
Сложность: medium

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

Длина пути между двумя узлами представлена количеством рёбер между ними.

Пример:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

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

1⃣Определить рекурсивную функцию solve(), принимающую текущий узел root и значение родительского узла parent. Если root равен NULL, вернуть 0. Рекурсивно вызвать solve() для левого и правого дочернего узлов, передав значение текущего узла как значение родительского узла.

2⃣Обновить переменную ans, если сумма значений для левого и правого узлов больше текущего значения ans. Если значение текущего узла равно значению родительского узла, вернуть max(left, right) + 1, иначе вернуть 0.

3⃣Вызвать solve() с корневым узлом и значением родительского узла -1. Вернуть максимальную длину пути ans..

😎 Решение:

class Solution {
    public $ans = 0;

    function solve($root, $parent) {
        if ($root === null) {
            return 0;
        }

        $left = $this->solve($root->left, $root->val);
        $right = $this->solve($root->right, $root->val);
        
        $this->ans = max($this->ans, $left + $right);
        
        return $root->val === $parent ? max($left, $right) + 1 : 0;
    }

    function longestUnivaluePath($root) {
        $this->solve($root, -1);
        return $this->ans;
    }
}

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