# 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`.

``````class Solution {
public:
int findClosestLeaf(TreeNode* root, int k) {
unordered_map<TreeNode*, TreeNode*> back;
TreeNode *kNode = find(root, k, back);
queue<TreeNode*> q{{kNode}};
unordered_set<TreeNode*> visited{{kNode}};
while (!q.empty()) {
TreeNode *t = q.front(); q.pop();
if (!t->left && !t->right) return t->val;
if (t->left && !visited.count(t->left)) {
visited.insert(t->left);
q.push(t->left);
}
if (t->right && !visited.count(t->right)) {
visited.insert(t->right);
q.push(t->right);
}
if (back.count(t) && !visited.count(back[t])) {
visited.insert(back[t]);
q.push(back[t]);
}
}
return -1;
}
TreeNode* find(TreeNode* node, int k, unordered_map<TreeNode*, TreeNode*>& back) {
if (node->val == k) return node;
if (node->left) {
back[node->left] = node;
TreeNode *left = find(node->left, k, back);
if (left) return left;
}
if (node->right) {
back[node->right] = node;
TreeNode *right = find(node->right, k, back);
if (right) return right;
}
return NULL;
}
};
``````

``````class Solution {
public:
int findClosestLeaf(TreeNode* root, int k) {
int res = -1, mn = INT_MAX;
unordered_map<int, int> m;
m[k] = 0;
find(root, k, m);
helper(root, -1, m, mn, res);
return res;
}
int find(TreeNode* node, int k, unordered_map<int, int>& m) {
if (!node) return -1;
if (node->val == k) return 1;
int r = find(node->left, k, m);
if (r != -1) {
m[node->val] = r;
return r + 1;
}
r = find(node->right, k, m);
if (r != -1) {
m[node->val] = r;
return r + 1;
}
return -1;
}
void helper(TreeNode* node, int cur, unordered_map<int, int>& m, int& mn, int& res) {
if (!node) return;
if (m.count(node->val)) cur = m[node->val];
if (!node->left && !node->right) {
if (mn > cur) {
mn = cur;
res = node->val;
}
}
helper(node->left, cur + 1, m, mn, res);
helper(node->right, cur + 1, m, mn, res);
}
};
``````

https://leetcode.com/problems/closest-leaf-in-a-binary-tree/

https://leetcode.com/problems/closest-leaf-in-a-binary-tree/discuss/109960/java-dfs-bfs-27ms

https://leetcode.com/problems/closest-leaf-in-a-binary-tree/discuss/109963/java-short-solution28-ms-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation