[LeetCode][117. Populating Next Right Pointers in Each Node II] 3 Approaches: BFS, BFS + LinkedList, Recursion

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4k 阅读时长 ≈ 4 分钟

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)\).

BFS + LinkedList

Each level can be seem as a Linked List.

For example, the root node is a linked list with one node, and the second level is a linked list with two nodes and so on…

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
   public Node connect_linkedlist(Node root) {
       if (root == null) {
           return root;
       }

       // the curNode as the linkedlist of each level
       Node curNode = root;
       while (curNode != null) {
           // a dummyNode to travesal current Level
           Node dummyNode = new Node(0);

           // the prev Node of next level
           Node prevNode = dummyNode;
           while (curNode != null) {
               if (curNode.left != null) {
                   // linked the left child
                   prevNode.next = curNode.left;
                   // update prev as LinkedList
                   prevNode = curNode.left;
               }

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

               // the next node of current level
               curNode = curNode.next;
           }

           // after process the next level, process 
           curNode = dummyNode.next;
       }

       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 static 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(1)\).

Recursion

It’s a little difficult but easy to get it.

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
public Node connect(Node root) {
    if (root == null || (root.left == null && root.right == null)) {
        return root;
    }

    if (root.left != null && root.right != null) {
        root.left.next = root.right;
        root.right.next = getNextHasChildrenNode(root);
    }

    if (root.left == null) {
        root.right.next = getNextHasChildrenNode(root);
    }

    if (root.right == null) {
        root.left.next = getNextHasChildrenNode(root);
    }

    // right should first
    root.right = connect(root.right);
    root.left = connect(root.left);

    return root;
}

public Node getNextHasChildrenNode(Node root) {
    while (root.next != null) {
        if (root.next.left != null) {
            return root.next.left;
        }
        if (root.next.right != null) {
            return root.next.right;
        }

        root = root.next;
    }

    return null;
}

Analysis

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

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗