Tree Breadth-First Search

Posted on

基本就是 deque 一把梭，不过需要单纯处理 root 为 None 的情况。借助同层节点的 index 可实现更细微的操作。

This pattern is based on the Breadth-First Search (BFS) technique to traverse a tree.

Any problem involving the traversal of a tree in a level-by-level order can be efficiently solved using this approach. We will use a queue to keep track of all the nodes of a level before we jump onto the next level. This also means that the space complexity of the algorithm will be O(W), where “W” is the maximum number of nodes on any level.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
if not root:
    return

queue = deque([root])
while queue:
    curr_len = len(queue)
    for idx in range(curr_len):
        node = queue.popleft()
        if idx != curr_len - 1:
            node.next = queue[0]

        # bfs
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

return root

LeetCode

102. Binary Tree Level Order Traversal
107. Binary Tree Level Order Traversal II
103. Binary Tree Zigzag Level Order Traversal
637. Average of Levels in Binary Tree
111. Minimum Depth of Binary Tree
429. N-ary Tree Level Order Traversal
117. Populating Next Right Pointers in Each Node II
116. Populating Next Right Pointers in Each Node
199. Binary Tree Right Side View