LeetCode 筆記 - 116. Populating Next Right Pointers in Each Node

題目在此 116. Populating Next Right Pointers in Each Node

給定一個 Perfect Binary Tree,請為每一個 node 的 next 指向右邊 node

解題思維

只要把每個節點該做的都做一做,其實就完成了
那因為是 Perfect Binary Tree,所以可以利用特性少做蠻多判斷的

我們要做的事情就只有兩件事

  • 把左子節點的 next 指向右子節點
  • 把右子節點的 next 指向 root 的左子節點

接著就每個 node 照這個邏輯做一次就完成了!

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
if not root or not root.left:
return root
root.left.next = root.right

if root.next:
root.right.next = root.next.left

self.connect(root.left)
self.connect(root.right)

return root

相關文章