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

Posted on

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

給定一個 Binary Tree，請為每一個 node 的 next 指向右邊 node
image 12

解題思維

這題的關鍵就是找出同一層的 node 有哪些
那在這裡 Breadth-First Search 剛好可以幫上我們的忙

透過搜索的順序，我們就可以知道 同一層的 node 有哪些

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""
# 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':
        
        if not root:
            return root
        
        upper_quque = [root]
        lower_quque = []
        
        while upper_quque:           
            last_node = None
            for node in upper_quque:
                if last_node:
                    last_node.next = node
                if node.left:
                    lower_quque.append(node.left)
                if node.right:
                    lower_quque.append(node.right)
                last_node = node
            upper_quque = lower_quque
            lower_quque = []
            
        return root

相關文章