By Long Luo

This article is the solution Traverse the Tree Level by Level: Standard BFS Solution of Problem 429. N-ary Tree Level Order Traversal.

Intuition

To traverse the tree level by level, we generally use breadth first search. In each round of breadth first search, we will traverse all nodes in the same layer.

For a typical BFS, we put the root node \(\textit{root}\) into the queue fist. In each round of BFS, we first record the number of nodes in the current queue, which is the number of nodes in the upper level.

After that, we remove the front of the queue to take the nodes out of the queue in turn until we get all the nodes of the upper level.

When this round of traversal is completed, we can get all nodes of the current level. In this way, when the BFS is completed, we can get the results.

By Long Luo

This article is the solution Why Use BFS? Search Every Possible Path vs Search A Possible Path of Problem 1091. Shortest Path in Binary Matrix .

Intuition

1. If we want to find a possible path, DFS will be more efficient. Because DFS will return a possible path if found, while it may not the shortest path.

2. BFS will try every possible path at the same time.

3. If we want to find the shortest of all possible paths, BFS is more efficient. It’s impossible for DFS to determine which is the shortest before trying all possible paths.

BFS

Use BFS to Level Traversal.

By Long Luo

This article is the solution 2 Approaches: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal) of Problem 1302. Deepest Leaves Sum.

Here shows 2 approaches to slove this problem: BFS(Level Order Travesal) and DFS(Get Max Depth, then Traversal).

BFS

To traverse the tree level by level, we generally use breadth first search. You can refer to this article Traverse the Tree Level by Level: Standard BFS Solution .

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

public int deepestLeavesSum(TreeNode root) {
    if (root == null) {
        return root.val;
    }

    int sum = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelCount = queue.size();
        boolean isDeepest = true;
        sum = 0;
        for (int i = 0; i < levelCount; i++) {
            TreeNode curNode = queue.poll();

            if (curNode.left == null && curNode.right == null) {
                sum += curNode.val;
            }

            if (curNode.left != null) {
                isDeepest = false;
                queue.offer(curNode.left);
            }

            if (curNode.right != null) {
                isDeepest = false;
                queue.offer(curNode.right);
            }
        }

        if (isDeepest && queue.isEmpty()) {
            return sum;
        }
    }

    return sum;
}

By Long Luo

This article is the solution 3 Approaches: BFS, BFS + LinkedList, Recursion of Problem 117. Populating Next Right Pointers in Each Node II .

Here shows 3 Approaches to slove this problem: BFS, BFS + LinkedList, Recursion.

BFS

Use BFS to level traversal, a List to store the Nodes of each level.

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

public Node connect_bfs(Node root) {
    if (root == null) {
        return root;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Node> levelNodes = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            Node curNode = queue.poll();
            levelNodes.add(curNode);
            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }

        for (int i = 0; i < levelNodes.size() - 1; i++) {
            Node node = levelNodes.get(i);
            node.next = levelNodes.get(i + 1);
        }
    }

    return root;
}

In fact, we just need a Node to store the Previous 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

public Node connect_bfs(Node root) {
    if (root == null) {
        return root;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelCount = queue.size();
        Node prev = null;
        for (int i = 0; i < levelCount; i++) {
            Node curNode = queue.poll();

            if (prev != null) {
                prev.next = curNode;
            }

            prev = curNode;

            if (curNode.left != null) {
                queue.add(curNode.left);
            }
            if (curNode.right != null) {
                queue.add(curNode.right);
            }
        }
    }

    return root;
}

Analysis

• Time Complexity: \(O(n)\).
• Space Complexity: \(O(n)\).

By Long Luo

This article is the solution Image Explanation: Distributing N Balls into 5 Boxes, Some Boxes May Be Empty of Problem 1641. Count Sorted Vowel Strings.

Math

Every vowel string is start by \(a, e, i, o, u\), and there are \(N\) strings.

How to distribute \(N\) strings into the \(5\) boxes, some boxes may be empty?

Imaging that there are \(N\) balls, we have to put them in to \(5\) boxes represented by the five vowels, as the picture shows.

Once the number of characters in each box were fixed, the string is fixed.

Therefore, how many ways are there to put \(N\) balls in \(5\) boxes, and the boxes can be empty?