LeetCode Populating Next Right Pointers in Each Node
2023-09-14 09:08:54 时间
LeetCode解题之Populating Next Right Pointers in Each Node
原题
为二叉树的节点都加入一个next指针,指向跟它在同一高度的右边的节点,假设右边没有节点,就指向None。
注意点:
- 最好仅仅用常量的空间
- 这是一棵全然二叉树
样例:
输入:
1
/ \
2 3
/ \ / \
4 5 6 7
输出:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
解题思路
这里採用了思路最清晰的解法,可是用的空间不是常量的。能够看出事实上就是把树的每一层都串联起来了。要处理每一层的节点。能够使用广度优先遍历,把每一层的节点暂存在列表中。再把这些节点都连接起来。
AC源代码
# Definition for binary tree with next pointer.
class TreeLinkNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
self.next = None
class Solution(object):
def connect(self, root):
"""
:type root: TreeLinkNode
:rtype: nothing
"""
if not root:
return
current_level = [root]
while current_level:
next_level = []
for node in current_level:
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
for i in range(len(next_level) - 1):
next_level[i].next = next_level[i + 1]
current_level = next_level
if __name__ == "__main__":
None
欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。
相关文章
- Leetcode 题目,分石子
- LeetCode周赛290,什么?你不会树状数组,这太不公平了
- ☆打卡算法☆LeetCode 201. 数字范围按位与 算法解析
- LeetCode排序链表C++解法(详解)
- 【day03】LeetCode(力扣)每日一刷[239. 滑动窗口最大值 ][1422. 分割字符串的最大得分][1046. 最后一块石头的重量 ]
- LeetCode 78.子集 - Go 实现
- LeetCode每日一题之817题链表组件
- 记录日志使用Node Redis实现快速的日志记录(node使用redis)
- 利用Node.js实现对MS SQL服务器的连接(node连MSsql)
- Node MSSQL 报错处理 解决技巧分享(node mssql报错)
- 使用Node.js链接/操作MS SQL数据库(node mssql使用)
- 轻松安装Oracle数据库Node环境下操作指南(node安装oracle)