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

Posted on
探討 LeetCode 第 116 題，在完美二元樹中為每個節點建立向右的 next 指針。本文利用完美二元樹的結構特性，透過遞迴邏輯將左子節點指向右子節點，並跨節點連接，提供簡潔高效的遍歷與指針設置解法。

題目在此 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

也許你也會想看看