By Long Luo

This article is the solution The Recursive Algorithm with Detailed Image Explanation of Problem 21. Merge Two Sorted Lists .

Intuition

We can use Recursion to solve this problem.

The key points of Recursion are \(2\).

1. How to terminate the recursion: Returns when either \(\texttt{l1}\) or \(\texttt{l2}\) is \(\texttt{null}\).

2. What to do in the process: if \(\texttt{l1.val} \le \texttt{l2.val}\), then point \(\texttt{l1.next}\) to the smaller of \(\texttt{l1}\) and \(\texttt{l2}\).

If \(\texttt{l1.val} \le \texttt{l2.val}\), we can choose the smaller node, such as \(\texttt{l1}\). However, the linked list is not reached the end, we will continue to compare.

Now we are compare \(\texttt{l1.next}\) and \(\texttt{l2}\). The \(\texttt{l1.next}\) and \(\texttt{l2}\) are processed in the recursive functions of the next layer.

We process such process and finally get the result.

By Long Luo

This article is the solution 4 Approaches: BFS, Memorization DFS, DP, Topo Sorting of Problem 329. Longest Increasing Path in a Matrix .

Here shows 4 Approaches to slove this problem: BFS, Memorization DFS, DP, Topological Sorting.

BFS

The simplest method that comes to my mind is BFS. We start search from each node, spread out like water, to see how far it can flood, and record the maximum flood path length of all nodes.

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
48
49
50
51
52
53
54
55
56
57
58
59

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int row = matrix.length;
        int col = matrix[0].length;
        if (row == 1 && col == 1) {
            return 1;
        }

        int max = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                max = Math.max(max, bfs(matrix, i, j));
            }
        }

        return max;
    }

    public int bfs(int[][] matrix, int x, int y) {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        int ans = 0;
        int row = matrix.length;
        int col = matrix[0].length;

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});

        while (!queue.isEmpty()) {
            int size = queue.size();
            ans++;

            for (int i = 0; i < size; i++) {
                int[] curPos = queue.poll();

                for (int[] dir : dirs) {
                    int nextX = curPos[0] + dir[0];
                    int nextY = curPos[1] + dir[1];

                    if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) {
                        continue;
                    }

                    if (matrix[nextX][nextY] <= matrix[curPos[0]][curPos[1]]) {
                        continue;
                    }

                    queue.offer(new int[]{nextX, nextY});
                }
            }
        }

        return ans;
    }
}

Analysis

• Time Complexity: \(O(m^2n^2)\).
• Space Complexity: \(O(mn)\).

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;
}