leetcode(二)

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 []

这里的做法:

  1. 先将用BFS(Breadth first search)算法将所有node的parent节点添加到treenode类的属性中,因为距离K的节点也有可能实在父节点的另外分支上,以及更上层的父节点的分支上,需要向上搜索。
  2. 然后再用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/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏儿童编程

我不是算命先生,却对占卜有了疑惑——如何论证“占卜前提”的正确与否

事出有因,我对《周易》感兴趣了很多年。只是觉得特别有趣,断断续续学习了一些皮毛。这几天又偶然接触到了《梅花易数》,觉得很是精彩,将五行八卦天干地支都串联了起来。...

13810
来自专栏儿童编程

什么样的人生才是有意义的人生——没有标准的标准答案

【导读】其实我们可以跳出这个小圈圈去更加科客观地看一下这个世界。在夜晚的时候我们仰望天空,浩瀚的宇宙中整个地球只是一粒浮尘,何况地球上一个小小的人类?在漫长的历...

1.7K50
来自专栏Ken的杂谈

【系统设置】CentOS 修改机器名

17230
来自专栏haifeiWu与他朋友们的专栏

复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

26440
来自专栏儿童编程

声音功能让儿童编程更有创造性

导读:Scratch中声音功能非常强大,除了常规的音效,你甚至可以模拟各种乐器的各个发音、设置节拍、休止……如果你愿意,甚至可以用它创作一个交响乐。我们可以引导...

13540
来自专栏儿童编程

儿童创造力教育与编程教育的碰撞——MIT雷斯尼克教授最新理论梗概

儿童编程教育已经在我国各一线二线城市疯狂出现,颇有“烂大街”的趋势。我们不禁要问很多很多问题:

21770
来自专栏儿童编程

天干地支五行八卦的对应关系

18790
来自专栏儿童编程

一张图理清《梅花易数》梗概

学《易经》的目的不一定是为了卜卦,但是了解卜卦绝对能够让你更好地了解易学。今天用一张思维导图对《梅花易数》的主要内容进行概括,希望能够给学友们提供帮助。

30840
来自专栏儿童编程

《动物魔法学校》儿童学编程Scratch之“外观”部分

导读:本文通过一个案例《动物魔法学校》来学习Scratch语言的“外观”部分。之后通过一系列其他功能的综合运用对作品功能进行了扩展。

18640
来自专栏FSociety

SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

5.1K20

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励