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 = , 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`.

742. Closest Leaf in a Binary Tree
``````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);
}

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();
if let Some(parent) = 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);
}
``````