742. Closest Leaf in a Binary Tree

Given a binary tree where every node has a unique value, and a target key k, find the value of the nearest leaf node to target k in the tree.

Here, nearest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input:
root = [1, 3, 2], k = 1
Diagram of binary tree:
          1
         / \
        3   2

Output: 2 (or 3)

Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.

Example 2:

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

Explanation: The nearest leaf node is the root node itself.

Example 3:

Input:
root = [1,2,3,4,null,null,null,5,null,6], k = 2
Diagram of binary tree:
             1
            / \
           2   3
          /
         4
        /
       5
      /
     6

Output: 3
Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.

Note:

  1. root represents a binary tree with at least 1 node and at most 1000 nodes.
  2. Every node has a unique node.val in range [1, 1000].
  3. There exists some node in the given binary tree for which node.val == k.

Rust Solution

struct Solution;
use rustgym_util::*;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;

#[derive(Default)]
struct Graph {
    edges: HashMap<i32, Vec<i32>>,
    nodes: HashMap<i32, bool>,
}

type Edge = (i32, bool);

trait Preorder {
    fn preorder(&self, parent: Option<i32>, graph: &mut Graph);
}

impl Preorder for TreeLink {
    fn preorder(&self, parent: Option<i32>, graph: &mut Graph) {
        if let Some(node) = self {
            let val = node.borrow().val;
            let left = &node.borrow().left;
            let right = &node.borrow().right;
            let is_leaf = left.is_none() && right.is_none();
            graph.add_node(val, is_leaf);
            if let Some(parent) = parent {
                graph.add_edge(parent, val);
                graph.add_edge(val, parent);
            }
            left.preorder(Some(val), graph);
            right.preorder(Some(val), graph);
        }
    }
}

impl Graph {
    fn add_node(&mut self, u: i32, is_leaf: bool) {
        *self.nodes.entry(u).or_default() = is_leaf;
    }
    fn add_edge(&mut self, u: i32, v: i32) {
        self.edges.entry(u).or_default().push(v);
    }
}

impl Solution {
    fn find_closest_leaf(root: TreeLink, k: i32) -> i32 {
        let mut graph: Graph = Graph::default();
        root.preorder(None, &mut graph);
        let mut queue: VecDeque<i32> = VecDeque::new();
        let mut visited: HashSet<i32> = HashSet::new();
        visited.insert(k);
        queue.push_back(k);
        while let Some(u) = queue.pop_front() {
            if graph.nodes[&u] {
                return u;
            } else {
                for &v in &graph.edges[&u] {
                    if visited.insert(v) {
                        queue.push_back(v);
                    }
                }
            }
        }
        0
    }
}

#[test]
fn test() {
    let root = tree!(1, tree!(3), tree!(2));
    let k = 1;
    let res = 3;
    assert_eq!(Solution::find_closest_leaf(root, k), res);
    let root = tree!(1);
    let k = 1;
    let res = 1;
    assert_eq!(Solution::find_closest_leaf(root, k), res);
    let root = tree!(
        1,
        tree!(2, tree!(4, tree!(5, tree!(6), None), None), None),
        tree!(3)
    );
    let k = 1;
    let res = 3;
    assert_eq!(Solution::find_closest_leaf(root, k), res);
}

Having problems with this solution? Click here to submit an issue on github.