［抄题］：
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.
[暴力解法]：
时间分析：
空间分析：
[优化后]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
［思维问题］：
不知道还要找点，把路径存在hashmap中
［英文数据结构或算法，为什么不用别的数据结构或算法］：
［一句话思路］：
bfs的过程中，cur节点的左、右、map中存储的路径都要放进q
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- dfs函数的作用是返回有效的 值为k的节点，所以结果是左右节点的时候也需要返回
- 左右节点均为空的时候，再返回root.val的数值
［二刷］：
- dfs函数中，先把左节点放进去，再返回整个的left
［三刷］：
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
用map存路径map.put(root.left, root);，然后用dfs找到k
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［算法思想：迭代/递归/分治/贪心］：
［关键模板化代码］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
[是否头一次写此类driver funcion的代码] ：
[潜台词] ：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int findClosestLeaf(TreeNode root, int k) {
//corner case
if (root == null) return -1; //initialiazation: map, q
//put first node into q, add left, right, route
HashMap<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
PriorityQueue<TreeNode> q = new PriorityQueue<TreeNode>();
TreeNode match = dfsTree(k, root, map); q.add(match);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
if (cur.left == null && cur.right == null) return cur.val;
if (cur.left != null) q.add(cur.left);
if (cur.right != null) q.add(cur.right);
if (map.containsKey(cur)) {
q.add(map.get(cur));
map.remove(cur);
}
} return -1;
} public TreeNode dfsTree(int k, TreeNode root, Map<TreeNode, TreeNode> map) {
//corner case : null
if (root == null) return null; //return if left & right is null
if (root.val == k) return root; //put left into map and return left
if (root.left != null) {
map.put(root.left, root);
TreeNode left = dfsTree(k, root.left, map);
if (left != null) return left;
} //put left into map and return left
if (root.right != null) {
map.put(root.right, root);
TreeNode right = dfsTree(k, root.right, map);
if (right != null) return right;
} //return null
return null;
}
}