← Static tasks

742. Closest Leaf in a Binary Tree

leetcode medium

#csharp#graph#hash-table#leetcode#medium#queue#search#tree#two-pointers

Task

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

Пример:

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

Output: 2

C# solution

matched/original
using System;
using System.Collections.Generic;
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
    public int FindClosestLeaf(TreeNode root, int k) {
        List<TreeNode> path = new List<TreeNode>();
        Dictionary<TreeNode, int> leaves = new Dictionary<TreeNode, int>();
        
        FindPath(root, k, path);
        FindLeaves(root, leaves);
        
        Queue<Tuple<TreeNode, int>> queue = new Queue<Tuple<TreeNode, int>>();
        queue.Enqueue(new Tuple<TreeNode, int>(path[path.Count - 1], 0));
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        
        while (queue.Count > 0) {
            var tuple = queue.Dequeue();
            TreeNode node = tuple.Item1;
            int dist = tuple.Item2;
            if (leaves.ContainsKey(node)) return node.val;
            visited.Add(node);
            if (node.left != null && !visited.Contains(node.left)) queue.Enqueue(new Tuple<TreeNode, int>(node.left, dist + 1));
            if (node.right != null && !visited.Contains(node.right)) queue.Enqueue(new Tuple<TreeNode, int>(node.right, dist + 1));
            if (path.Count > 1) queue.Enqueue(new Tuple<TreeNode, int>(path[path.Count - 2], dist + 1)), path.RemoveAt(path.Count - 1);
        }
        return -1;
    }
    
    private bool FindPath(TreeNode node, int k, List<TreeNode> path) {
        if (node == null) return false;
        path.Add(node);
        if (node.val == k) return true;
        if (FindPath(node.left, k, path) || FindPath(node.right, k, path)) return true;
        path.RemoveAt(path.Count - 1);
        return false;
    }
    
    private void FindLeaves(TreeNode node, Dictionary<TreeNode, int> leaves) {
        if (node == null) return;
        if (node.left == null && node.right == null) leaves[node] = 0;
        FindLeaves(node.left, leaves);
        FindLeaves(node.right, leaves);
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
public:
    public int FindClosestLeaf(TreeNode root, int k) {
        List<TreeNode> path = new List<TreeNode>();
        unordered_map<TreeNode, int> leaves = new unordered_map<TreeNode, int>();
        
        FindPath(root, k, path);
        FindLeaves(root, leaves);
        
        queue<Tuple<TreeNode, int>> queue = new queue<Tuple<TreeNode, int>>();
        queue.Enqueue(new Tuple<TreeNode, int>(path[path.size() - 1], 0));
        HashSet<TreeNode> visited = new HashSet<TreeNode>();
        
        while (queue.size() > 0) {
            var tuple = queue.Dequeue();
            TreeNode node = tuple.Item1;
            int dist = tuple.Item2;
            if (leaves.count(node)) return node.val;
            visited.push_back(node);
            if (node.left != null && !visited.Contains(node.left)) queue.Enqueue(new Tuple<TreeNode, int>(node.left, dist + 1));
            if (node.right != null && !visited.Contains(node.right)) queue.Enqueue(new Tuple<TreeNode, int>(node.right, dist + 1));
            if (path.size() > 1) queue.Enqueue(new Tuple<TreeNode, int>(path[path.size() - 2], dist + 1)), path.RemoveAt(path.size() - 1);
        }
        return -1;
    }
    
    private bool FindPath(TreeNode node, int k, List<TreeNode> path) {
        if (node == null) return false;
        path.push_back(node);
        if (node.val == k) return true;
        if (FindPath(node.left, k, path) || FindPath(node.right, k, path)) return true;
        path.RemoveAt(path.size() - 1);
        return false;
    }
    
    private void FindLeaves(TreeNode node, unordered_map<TreeNode, int> leaves) {
        if (node == null) return;
        if (node.left == null && node.right == null) leaves[node] = 0;
        FindLeaves(node.left, leaves);
        FindLeaves(node.right, leaves);
    }
}

Java solution

matched/original
import java.util.*;

public class Solution {
    public int findClosestLeaf(TreeNode root, int k) {
        List<TreeNode> path = new ArrayList<>();
        Map<TreeNode, Integer> leaves = new HashMap<>();
        
        findPath(root, k, path);
        findLeaves(root, leaves);
        
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(path.get(path.size() - 1), 0));
        Set<TreeNode> visited = new HashSet<>();
        
        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> pair = queue.poll();
            TreeNode node = pair.getKey();
            int dist = pair.getValue();
            if (leaves.containsKey(node)) return node.val;
            visited.add(node);
            if (node.left != null && !visited.contains(node.left)) queue.add(new Pair<>(node.left, dist + 1));
            if (node.right != null && !visited.contains(node.right)) queue.add(new Pair<>(node.right, dist + 1));
            if (path.size() > 1) queue.add(new Pair<>(path.remove(path.size() - 1), dist + 1));
        }
        return -1;
    }
    
    private boolean findPath(TreeNode node, int k, List<TreeNode> path) {
        if (node == null) return false;
        path.add(node);
        if (node.val == k) return true;
        if (findPath(node.left, k, path) || findPath(node.right, k, path)) return true;
        path.remove(path.size() - 1);
        return false;
    }
    
    private void findLeaves(TreeNode node, Map<TreeNode, Integer> leaves) {
        if (node == null) return;
        if (node.left == null && node.right == null) leaves.put(node, 0);
        findLeaves(node.left, leaves);
        findLeaves(node.right, leaves);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }
    public K getKey() { return key; }
    public V getValue() { return value; }
}

JavaScript solution

matched/original
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;
};

Python solution

matched/original
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findClosestLeaf(root, k):
    from collections import deque, defaultdict
    
    def find_path(node, k, path):
        if not node:
            return False
        path.append(node)
        if node.val == k:
            return True
        if (node.left and find_path(node.left, k, path)) or (node.right and find_path(node.right, k, path)):
            return True
        path.pop()
        return False
    
    def find_leaves(node, leaves):
        if not node:
            return
        if not node.left and not node.right:
            leaves[node] = 0
        find_leaves(node.left, leaves)
        find_leaves(node.right, leaves)
    
    path = []
    find_path(root, k, path)
    
    leaves = {}
    find_leaves(root, leaves)
    
    queue = deque([(path[-1], 0)])
    visited = set()
    
    while queue:
        node, dist = queue.popleft()
        if node in leaves:
            return node.val
        visited.add(node)
        if node.left and node.left not in visited:
            queue.append((node.left, dist + 1))
        if node.right and node.right not in visited:
            queue.append((node.right, dist + 1))
        if len(path) > 1 and path[-2] not in visited:
            queue.append((path.pop(), dist + 1))
    return -1

Go solution

matched/original
package main

import "container/list"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func findClosestLeaf(root *TreeNode, k int) int {
    path := []*TreeNode{}
    leaves := map[*TreeNode]int{}
    
    findPath(root, k, &path)
    findLeaves(root, leaves)
    
    queue := list.New()
    queue.PushBack([2]interface{}{path[len(path)-1], 0})
    visited := map[*TreeNode]bool{}
    
    for queue.Len() > 0 {
        elem := queue.Front()
        queue.Remove(elem)
        node, dist := elem.Value.([2]interface{})[0].(*TreeNode), elem.Value.([2]interface{})[1].(int)
        if _, ok := leaves[node]; ok {
            return node.Val
        }
        visited[node] = true
        if node.Left != nil && !visited[node.Left] {
            queue.PushBack([2]interface{}{node.Left, dist + 1})
        }
        if node.Right != nil && !visited[node.Right] {
            queue.PushBack([2]interface{}{node.Right, dist + 1})
        }
        if len(path) > 1 {
            queue.PushBack([2]interface{}{path[len(path)-2], dist + 1})
            path = path[:len(path)-1]
        }
    }
    return -1
}

func findPath(node *TreeNode, k int, path *[]*TreeNode) bool {
    if node == nil {
        return false
    }
    *path = append(*path, node)
    if node.Val == k {
        return true
    }
    if findPath(node.Left, k, path) || findPath(node.Right, k, path) {
        return true
    }
    *path = (*path)[:len(*path)-1]
    return false
}

func findLeaves(node *TreeNode, leaves map[*TreeNode]int) {
    if node == nil {
        return
    }
    if node.Left == nil && node.Right == nil {
        leaves[node] = 0
    }
    findLeaves(node.Left, leaves)
    findLeaves(node.Right, leaves)
}

Explanation

Algorithm

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

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

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

😎