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':
# 當根節點為空的時候直接回傳
if not root:return
# 存在左兒子，將左兒子的next指向右兒子
if root.left:
root.left.next = root.right
# 注意這里，如果root.next存在，表示root同城右邊還有節點
# 就需要將root的右兒子指向root右邊節點的左兒子
if root.next:
root.right.next = root.next.left
# 注意這里一定要先遞回左子樹
self.connect(root.left)
self.connect(root.right)
return root
# 迭代的方法
# 程序跟遞回很類似，
def connect(self, root: 'Node') -> 'Node':
# 重新定義一個變數，用于遍歷二叉樹
node1 = root
# 進行回圈
while node1:
# 重新定義一個變數，用于遍歷當前層節點
node2 = node1
while node2:
# 左兒子存在，指向右兒子
if node2.left:
node2.left.next = node2.right
# 當前節點存在右邊節點，而且右兒子存在
# 就需要將當前節點的右兒子指向當前節點右邊節點的左兒子
if node2.next and node2.right :
node2.right.next = node2.next.left
# 遍歷下一個節點
node2 = node2.next
# 注意這里要指向左兒子
node1 = node1.left
return root
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/105980.html
標籤：Python
上一篇：115不同的子序列