## 题目描述：

LeetCode 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 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 = , 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:

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

## 解题思路：

```递归遍历二叉树：

找到值为k的节点knode，所有叶子节点leaves，构造字典parents存储节点值到其父节点的映射

求leaf的所有祖先节点（由近及远），记为leafParents

kParents和leafParents的公共部分即k到leaf的路径，更新答案```

## Python代码：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def findClosestLeaf(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
parents = {}
leaves = []
self.knode = None
def traverse(root):
if root.val == k: self.knode = root
if not root.left and not root.right:
leaves.append(root)
return
for child in (root.left, root.right):
if not child: continue
traverse(child)
parents[child.val] = root
def findParents(node):
ans = [node.val]
while node.val in parents:
node = parents[node.val]
ans.append(node.val)
return ans
traverse(root)
kParents = findParents(self.knode)
ans, dist = None, 0x7FFFFFFF
for leaf in leaves:
leafParents = findParents(leaf)
cross = [n for n in leafParents if n in kParents]
ndist = leafParents.index(cross) + kParents.index(cross)
if ndist < dist:
dist = ndist
ans = leaf
return ans.val
``````

Pingbacks已关闭。