【Leetcode】116. Populating Next Right Pointers in Each Node

1 因为是perfect binary tree,所以所有叶子节点都在一个level上,而且每一个internal node都有两个children

2 BFS不能用queue来做,因为会有extra space

3 最外面一个while循环,循环条件是root.left

4 将当前节点root的root.left和root.right连接起来后(root.left.next=root.right),我们需要再将root.right和root.next.left连接起来,直到root.next不再存在

5 在init里,self.next = None已经

6 if not root: return 不能写成if not root: return None 这道题并没有返回值,不能用return None


Time complexity: O(n)

Space complexity: O(n) since the last level has n/2 nodes


Time complexity: O(n)

Space complexity: O(1)

Tree上的node一开始就是定义成有next pointer的,不需要额外再处理了

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容