0742：二叉树最近的叶节点（★）

2017-01-11 约 439 字预计阅读 1 分钟次阅读

力扣第 742 题

题目

给定一个 每个结点的值互不相同 的二叉树，和一个目标整数值 k，返回树中与目标值 k 最近的叶结点 。

与叶结点最近 表示在二叉树中到达该叶节点需要行进的边数与到达其它叶结点相比最少。而且，当一个结点没有孩子结点时称其为叶结点。

示例 1：

输入：root = [1, 3, 2], k = 1
输出： 2
解释： 2 和 3 都是距离目标 1 最近的叶节点。

示例 2：

输入：root = [1], k = 1
输出：1
解释：最近的叶节点是根结点自身。

示例 3：

输入：root = [1,2,3,4,null,null,null,5,null,6], k = 2
输出：3
解释：值为 3（而不是值为 6）的叶节点是距离结点 2 的最近结点。

提示：

二叉树节点数在 [1, 1000] 范围内
1 <= Node.val <= 1000
每个节点值都不同
给定的二叉树中有某个结点使得 node.val == k

分析

先建树对应的无向图，然后 bfs 找最近的叶节点即可。

注意有根节点的干扰，不能根据节点的度数来判断，所以建图时先记录所有叶节点。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


def findClosestLeaf(self, root: Optional[TreeNode], k: int) -> int:
	nxt = defaultdict(list)
	stack, leaf = [root], set()
	while stack:
		u = stack.pop()
		if not u.right and not u.left:
			leaf.add(u.val)
			continue
		for v in [u.right,u.left]:
			if v:
				stack.append(v)
				nxt[u.val].append(v.val)
				nxt[v.val].append(u.val)
	Q, vis = deque([k]), {k}
	while Q:
		u = Q.popleft()
		if u in leaf:
			return u
		for v in nxt[u]:
			if v not in vis:
				Q.append(v)
				vis.add(v)

60 ms

目录

0742：二叉树最近的叶节点（★）

题目

分析

解答