Задача: 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 {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

var findClosestLeaf = function(root, k) {
    function findPath(node, k, path) {
        if (!node) return false;
        path.push(node);
        if (node.val === k) return true;
        if ((node.left && findPath(node.left, k, path)) || (node.right && findPath(node.right, k, path))) return true;
        path.pop();
        return false;
    }
    
    function findLeaves(node, leaves) {
        if (!node) return;
        if (!node.left && !node.right) leaves.set(node, 0);
        findLeaves(node.left, leaves);
        findLeaves(node.right, leaves);
    }
    
    let path = [];
    findPath(root, k, path);
    
    let leaves = new Map();
    findLeaves(root, leaves);
    
    let queue = [[path[path.length - 1], 0]];
    let visited = new Set();
    
    while (queue.length) {
        let [node, dist] = queue.shift();
        if (leaves.has(node)) return node.val;
        visited.add(node);
        if (node.left && !visited.has(node.left)) queue.push([node.left, dist + 1]);
        if (node.right && !visited.has(node.right)) queue.push([node.right, dist + 1]);
        if (path.length > 1) queue.push([path.pop(), dist + 1]);
    }
    return -1;
};

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