Задача: 742. Closest Leaf in a Binary Tree
Сложность: medium

Если задан корень бинарного дерева, в котором каждый узел имеет уникальное значение, а также задано целое число k, верните значение ближайшего к цели k узла листа дерева. Ближайший к листу узел означает наименьшее количество ребер, пройденных бинарным деревом, чтобы достичь любого листа дерева. Кроме того, узел называется листом, если у него нет дочерних узлов.

Пример:

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

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

1⃣Пройдите дерево, чтобы найти путь от корня до узла k и сохранить его в список.

2⃣Найдите все листья и минимальное расстояние до них, используя BFS, начиная с найденного узла k.

3⃣Верните значение ближайшего листа.

😎 Решение:

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function findClosestLeaf($root, $k) {
    $path = [];
    $leaves = [];
    
    function findPath($node, $k, &$path) {
        if (!$node) return false;
        $path[] = $node;
        if ($node->val == $k) return true;
        if (findPath($node->left, $k, $path) || findPath($node->right, $k, $path)) return true;
        array_pop($path);
        return false;
    }
    
    function findLeaves($node, &$leaves) {
        if (!$node) return;
        if (!$node->left && !$node->right) $leaves[spl_object_hash($node)] = 0;
        findLeaves($node->left, $leaves);
        findLeaves($node->right, $leaves);
    }
    
    findPath($root, $k, $path);
    findLeaves($root, $leaves);
    
    $queue = [[end($path), 0]];
    $visited = [];
    
    while ($queue) {
        list($node, $dist) = array_shift($queue);
        if (isset($leaves[spl_object_hash($node)])) return $node->val;
        $visited[spl_object_hash($node)] = true;
        if ($node->left && !isset($visited[spl_object_hash($node->left)])) $queue[] = [$node->left, $dist + 1];
        if ($node->right && !isset($visited[spl_object_hash($node->right)])) $queue[] = [$node->right, $dist + 1];
        if (count($path) > 1) $queue[] = [array_pop($path), $dist + 1];
    }
    return -1;
}

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