LeetCode 筆記 - 919. Complete Binary Tree Inserter

Posted on

題目在此 919. Complete Binary Tree Inserter

簡單說就是實作一個操作完全二元樹的 class，初始給你的二元樹也會是完全二元樹。

解題思維

如果不清楚什麼是完全二元樹，可以先參考 Complete Binary Tree - Wikipedia

這題的關鍵在於如何快速地找到目前需要 insert 新節點的 parent。
為此我們可以在一開始使用 Breadth-First Search 來找到未來可以當作新節點的 parent 清單。

step 0: 將 root 跑過一次 Breadth-First Search，途中可以按照 Breadth-First Search 看到節點的順序，將 left or right 是空的節點加入 parent_queue。
step 1: 新增節點時，從 parent_queue 中 pop 出一個節點，並將新節點加入 parent_queue。如果 pop 出來的節點 left 跟 right 都有新節點了，則從 parent_queue 釋出。image 106

剩下就是 Breadth-First Search的基本操作了。

程式碼

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
35
36
37
38
39
40
41
42
43
44
45
46
47
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class CBTInserter:

    def __init__(self, root: Optional[TreeNode]):
        self.root = root
        self.parent_queue = []

        self.bfs_queue = []
        self.bfs(root)

    def bfs(self, node):
        if not node:
            return

        if node.left is not None:
            self.bfs_queue.append(node.left)
        if node.right is not None:
            self.bfs_queue.append(node.right)

        if node.left is None or node.right is None:
            self.parent_queue.append(node)

        if self.bfs_queue:
            next_node = self.bfs_queue.pop(0)
            self.bfs(next_node)

    def insert(self, val: int) -> int:

        new_node = TreeNode(val)
        self.parent_queue.append(new_node)

        current_parent = self.parent_queue[0]
        if current_parent.left is None:
            current_parent.left = new_node
        else:
            current_parent.right = new_node
            self.parent_queue.pop(0)

        return current_parent.val

    def get_root(self) -> Optional[TreeNode]:
        return self.root
image 106

也許你也會想看看