LWC 62：742. Closest Leaf in a Binary Tree
LWC 62：742. Closest Leaf in a Binary Tree
LWC 62：742. Closest Leaf in a Binary Tree
传送门：742. Closest Leaf in a Binary Tree
Problem:
Given a binary tree where every node has a unique value, and a target key k, find the closest leaf node to target k in the tree. 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 closest leaf node to 1.
Example 2:
Input: root = 1, k = 1 Output: 1 Explanation: The closest 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 closest to the node with value 2.
Note:
root represents a binary tree with at least 1 node and at most 1000 nodes.
Every node has a unique node.val in range [1, 1000].
There exists some node in the given binary tree for which node.val == k.
思路： 给定某个结点k，求离k最近的叶子结点是谁。实际上可以把树看作为无向图，所以问题就转化为求k到任意结点的最短距离。当然此处答案在叶子结点中更新即可。还需注意：在树构成的无向图中，每两个结点之间的路径只会存在一条，所以才无脑递归或者无脑bfs。具体怎么无脑参看代码。
Java 递归版本：
List<Integer>[] graph;
List<Integer> leaves;
int[] dist;
void add(int from, int to) {
graph[from].add(to);
graph[to].add(from);
}
void dfs(TreeNode root) {
if (root == null) return;
if (root.left == null && root.right == null) leaves.add(root.val);
if (root.left != null) add(root.val, root.left.val);
if (root.right != null) add(root.val, root.right.val);
dfs(root.left);
dfs(root.right);
}
void efs(int x, int p, int d) {
dist[x] = d;
for (int to : graph[x]) {
if (to != p) efs(to, x, d + 1);
}
}
public int findClosestLeaf(TreeNode root, int k) {
int INF = 0x3f3f3f3f;
graph = new ArrayList[1016];
leaves = new ArrayList<>();
dist = new int[1016];
Arrays.fill(dist, INF);
for (int i = 0; i < 1016; ++i) graph[i] = new ArrayList<>();
// 树转无向图，并求得叶子结点
dfs(root);
// 无脑k出发到其他所有结点的最短路径
efs(k, -1, 0);
int min = INF;
int minNode = -1;
for (int leaf : leaves) {
if (dist[leaf] < min) {
min = dist[leaf];
minNode = leaf;
}
}
return minNode;
}Python 广搜版本：
def findClosestLeaf(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
leaves = set()
graph = [[] for _ in xrange(1016)]
def traverse(root):
if not root: return
if not root.left and not root.right: leaves.add(root.val)
if root.left:
graph[root.val].append(root.left.val)
graph[root.left.val].append(root.val)
if root.right:
graph[root.val].append(root.right.val)
graph[root.right.val].append(root.val)
traverse(root.left)
traverse(root.right)
traverse(root)
dist = [0] * 1016
pq = []
pq.append((0, k))
dist[k] = 0
vis = set()
vis.add(k)
while len(pq):
cur = pq.pop(0)
if cur[1] in leaves: return cur[1]
for to in graph[cur[1]]:
if to not in vis:
dist[to] = cur[0] + 1
pq.append((cur[0] + 1, to))
vis.add(to)