"""
# Definition for a Node.
class Node(object):
def __init__(self, val, left, right, next):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
def helper(root):
if not root:
return
if not root.left and not root.right:
return
# start 是当前节点的左子树指向下一个不是亲兄弟节点的节点
if root.left and root.right:
root.left.next = root.right
start = root.right
elif root.left:
start = root.left
else:
start = root.right
next = root.next
while next:
if not next.left and not next.right:
next = next.next
continue
if next.left:
end = next.left
start.next = end
break
else:
end = next.right
start.next = end
break
# 这里之前是先left 再right 报错 未通过
# 看了评论 说要先递归 rigth 换了位置 通过
helper(root.right)
helper(root.left)
helper(root)
return root
# leetcode 时间最短
class Solution1(object):
def findnext(self, root):
while root != None:
if root.left != None:
return root.left
if root.right != None:
return root.right
root = root.next
return None
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if root == None:
return root
p = root
nextfirst = None
while p != None:
while p != None:
if p.left != None:
if p.right != None:
p.left.next = p.right
else:
p.left.next = self.findnext(p.next)
if nextfirst == None:
nextfirst = p.left
if p.right != None:
p.right.next = self.findnext(p.next)
if nextfirst == None:
nextfirst = p.right
p = p.next
p = nextfirst
nextfirst = None
return root
# leetcode时间第二短
class Solution2(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
if not root:
return
res, cur_level = [], [root]
while cur_level:
next_level = []
for node in cur_level:
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
res.append(cur_level)
cur_level = next_level
for cur_level in res:
for i in range(len(cur_level) - 1):
cur_level[i].next = cur_level[i + 1]
return root
# leetcode 时间第三短
class Solution3(object):
def connect(self, root):
"""
:type root: Node
:rtype: Node
"""
# 层次遍历咯#
root1 = root
stack = [root]
if not root:
return None
root.next = None
while len(stack) > 0:
temp = []
for i in range(len(stack)):
if i < len(stack) - 1:
stack[i].next = stack[i + 1]
else:
stack[i].next = None
if stack[i].left:
temp.append(stack[i].left)
if stack[i].right:
temp.append(stack[i].right)
stack = temp
return root1
网友评论