leetcode题解记录-116填充每个节点的下一个右侧节点指针（python3）

题目

填充每个节点的下一个右侧节点指针
题目链接
官方题解

关键词

完美二叉树，层次遍历

代码记录

方法一 层次遍历

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
    	cur_q=[root]
    	while cur_q:
    		for i in range(len(cur_q)-1):
    			cur_q[i].next=cur_q[i+1]
    		next_q=[]
    		for i in range(len(cur_q)):
    			node=cur_q[i]
    			if node and node.left:
    				next_q.append(node.left)
    			if node and node.right:
    				next_q.append(node.right)
    		cur_q=next_q
    	return roo

方法二 使用已建立的 next 指针

class Solution:
	def connect(self,root):
		if not root:
			return None
		leftmost=root
		while leftmost:
			head=leftmost
			while head and head.left:
				head.left.next=head.right
				if head.next:
					head.right.next=head.next.left
				head=head.next
			leftmost=leftmost.left
		return root