[LeetCode] 117. Populating Next Right Pointers in Each Node II

Posted on | In

Problem

Given a binary tree

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

117. Populating Next Right Pointers in Each Node II

1
Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

1
Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}

1
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

  • You may only use constant extra space.
  • Recursive approach is fine, implicit stack space does not count as extra space for this problem.

Explanation 1

  1. Similar to 116. Populating Next Right Pointers in Each Node, if we want to use recursion method, we can first make a pointer that points to the current node’s next node. Then, we find this pointer’s left most node. And we use the current node’s right node points to that left most node we found, and the current node’s left node points to the current node’s right node like the last problem.

  2. Recursivly apply the above method to the current node’s right node and left node. The base case is if the root node is NULL, we can just return.

Solution 1

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
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        TreeLinkNode p = root.next;
        while (p != null) {
            if (p.left != null) {
                p = p.left;
                break;
            }
            if (p.right != null) {
                p = p.right;
                break;
            }
            p = p.next;
        }
        if (root.right != null) root.right.next = p;
        if (root.left != null) {
            if (root.right != null) root.left.next = root.right;
            else root.left.next = p;
        }
        connect(root.right);
        connect(root.left);
    }
}

Explanation 2

  1. This solution uses O(1) space and it is iterating level by level. First, we create a dummy list that is used to pointing to each level’s element before the first element. We create a cur pointer that is used to iterate the current level’s element, it connects its current node’s sub node’s next. First, if the left subnode exists, cur.next connects it, then iterate cur = cur.next. If the right subnode exists, cur.next connects it, then iterate cur = cur.next. Now, the root’s left and right subnodes are connected. Then, we move root to the right. After we move, if root is not exist, then it means we finish connecting to current root node’s sub node. We then reset root to dummy’s next node, cur reset pointing to dummy, and we set dummy’s next to null because we want the cur pointer’s next to NULL so that we can use cur.next to point to the first element in the next level.

Solution 2

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
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        TreeLinkNode dummy = new TreeLinkNode(-1);
        dummy.next = root;
        TreeLinkNode cur = dummy;
        while (root != null) {
            if (root.left != null) {
                cur.next = root.left;
                cur = cur.next;
            }
            if (root.right != null) {
                cur.next = root.right;
                cur = cur.next;
            }

            root = root.next;
            if (root == null) {
                root = dummy.next;
                cur = dummy;
                dummy.next = null;
            }
        }
    }
}