Задача: 513. Find Bottom Left Tree Value
Сложность: medium

Дан корень двоичного дерева, верните самое левое значение в последней строке дерева.

Пример:

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

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

1⃣Инициализируйте переменную maxDepth для хранения глубины нижнего уровня дерева. Инициализируйте переменную bottomLeftValue для хранения самого левого значения в последней строке дерева.

2⃣Реализуйте рекурсивную функцию dfs, которая обходит дерево и находит самое левое значение в последней строке дерева. Параметры функции: current (текущий узел) и depth (его глубина). Проверьте, пуст ли текущий узел. Если да, то вернитесь.

3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎 Решение:

class Solution {
    private $maxDepth = -1;
    private $bottomLeftValue = 0;
    
    function findBottomLeftValue($root) {
        $this->dfs($root, 0);
        return $this->bottomLeftValue;
    }
    
    private function dfs($current, $depth) {
        if ($current == null) return;
        
        if ($depth > $this->maxDepth) {
            $this->maxDepth = $depth;
            $this->bottomLeftValue = $current->val;
        }
        
        $this->dfs($current->left, $depth + 1);
        $this->dfs($current->right, $depth + 1);
    }
}

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