# LWC 62：742. Closest Leaf in a Binary Tree

## LWC 62：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.

Java 递归版本：

```    List<Integer>[]  graph;
List<Integer> leaves;
int[] dist;

void add(int from, int to) {
}

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()

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))

0 条评论

## 相关文章

12320

57320

### LeetCode 144. Binary Tree Preorder Traversal题目分析代码

Given a binary tree, return the preorder traversal of its nodes' values. For ex...

10320

7820

### 用OC和Swift一起说说二叉树

一：在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）...

10850

13220

25150

### 111.Minimum Depth of Binary Tree(Tree-Easy)

Given a binary tree, find its minimum depth. The minimum depth is the number of ...

22290

65290

### 51 Nod 1008 N的阶乘 mod P【Java大数乱搞】

1008 N的阶乘 mod P 基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 输入N和P（P为质数），求N! Mod P ...

28760