leetcode(二)
leetcode(二)
努力努力再努力F
发布于 2018-09-11 11:15:29
发布于 2018-09-11 11:15:29
leetcode_problem863
rank: medium
1.问题
给定一个二叉数（root），二叉树中一个node（target）以及整数K，求二叉树中所有与target距离K的节点值。问题描述与example如下。
2.解决方案
1 # Definition for a binary tree node.
2 # class TreeNode:
3 # def __init__(self, x):
4 # self.val = x
5 # self.left = None
6 # self.right = None
7
8 class Solution:
9 def distanceK(self, root, target, K):
10 """
11 :type root: TreeNode
12 :type target: TreeNode
13 :type K: int
14 :rtype: List[int]
15 """
16 def bfs(node,par=None): # give each node add parent_node
17 if node:
18 node.par = par
19 bfs(node.left, node)
20 bfs(node.right, node)
21
22 bfs(root)
23
24 queue = collections.deque([(target,0)]) # queue structure initial
25 seen = {target} #in order to aviod checking repeat node
26 while queue:
27 if queue[0][1] == K:
28 return [node.val for node, d in queue]
29 node, d = queue.popleft()
30 for nei in (node.left, node.right, node.par):
31 if nei and nei not in seen:
32 seen.add(nei)
33 queue.append((nei, d+1))
34
35 return []这里的做法：
- 先将用BFS（Breadth first search）算法将所有node的parent节点添加到treenode类的属性中，因为距离K的节点也有可能实在父节点的另外分支上，以及更上层的父节点的分支上，需要向上搜索。
- 然后再用BFS算法去搜索离目标节点K距离的所有节点，这里建立了一个deque（double ended queue）来存储节点以及他对应的距离，建立seen集合，用来避免重复检查节点和队列距离乱序，因为算法会从target的左右节点和父结点出发搜索，然后又从左右节点和父结点的左右节点和父结点出发去搜索，可以看到target的左节点的父结点还是target，所以不加seen，不仅会造成队列判断条件复杂，而且会造成很大的冗余，这是很低效的。最好是自己画一棵二叉树实例，一步一步分析算法，就是知道该方法是多么巧妙。
参考solution中还有一种使用DFS（depth first search）的方法，个人觉得那种过于复杂，还是上述方法比较简单直观，有兴趣的话可以看看。
参考
1. https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/solution/
2. https://leetcode.com/contest/weekly-contest-91/problems/all-nodes-distance-k-in-binary-tree/
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-07-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读