Question

Formatted question description: https://leetcode.ca/all/117.html

117. Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:
    You may only use constant extra space.

For example,
Given the following binary tree,
         1
       /  \
      2    3
     / \    \
    4   5    7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

@tag-tree

Algorithm

DFS

Since the subtree may be incomplete, it is necessary to scan the nodes in the same layer of the parent node in parallel to find their left and right child nodes.

BFS

Same as in 116 - Populating Next Right Pointers in Each Node.

Code

public class Populating_Next_Right_Pointers_in_Each_Node_II {

    public static void main(String[] args) {
        Populating_Next_Right_Pointers_in_Each_Node_II out = new Populating_Next_Right_Pointers_in_Each_Node_II();

        Solution_fancy s = out.new Solution_fancy();

        TreeLinkNode root = new TreeLinkNode(1);
        root.left = new TreeLinkNode(2);
        root.right = new TreeLinkNode(3);
        root.left.left = new TreeLinkNode(4);
        root.left.right = new TreeLinkNode(5);
        root.right.left = new TreeLinkNode(6);
        root.right.right = new TreeLinkNode(7);

        s.connect(root);
    }

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

            Queue<TreeLinkNode> q = new LinkedList<>();

            TreeLinkNode levelEndMarker = new TreeLinkNode(0);
            TreeLinkNode prev = new TreeLinkNode(0);

            q.offer(root);
            q.offer(levelEndMarker);

            while (!q.isEmpty()) {
                TreeLinkNode current = q.poll();

                if (current == levelEndMarker) {
                    // push marker again as next level end
                    if (!q.isEmpty()) { // @note: missed final check again...
                        q.offer(levelEndMarker);
                    }

                    // first node of each level, can not be last of upper level
                    prev = levelEndMarker; // can be any node which is not in this tree
                    continue;
                }

                if (current.left != null) {
                    q.offer(current.left);
                }
                if (current.right != null) {
                    q.offer(current.right);
                }

                prev.next = current;
                prev = current;
            }
        }
    }

    class Solution_fancy {
        public TreeLinkNode connect(TreeLinkNode root) {
            TreeLinkNode dummyHead = new TreeLinkNode(0); // this head will always point to the first element in the current layer we are searching
            TreeLinkNode pre = dummyHead; // this 'pre' will be the "current node" that builds every single layer
            TreeLinkNode real_root = root; // just for return statement

            while (root != null) {
                if (root.left != null) {
                    pre.next = root.left; // @note: here pre is same as dummyHead, pointing to 1st node of this level. this is before pre is updated to be other nodes
                    pre = pre.next;
                }
                if (root.right != null) {
                    pre.next = root.right;
                    pre = pre.next;
                }
                root = root.next;
                if (root == null) { // reach the end of current layer
                    pre = dummyHead; // shift pre back to the beginning, get ready to point to the first element in next layer
                    root = dummyHead.next;
                    ;//root comes down one level below to the first available non null node
                    dummyHead.next = null;//reset dummyhead back to default null, so that later it will point to next level's first node
                }
            }
            return real_root;
        }
    }


}

// OJ: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
// Time: O(N)
// Space: O(H)
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        Node head, *tail = &head;
        for (auto node = root; node; node = node->next) {
            if (node->left) {
                tail->next = node->left;
                tail = tail->next;
            }
            if (node->right) {
                tail->next = node->right;
                tail = tail->next;
            }
        }
        connect(head.next);
        return root;
    }
};

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: "Node") -> "Node":
        def modify(curr):
            nonlocal prev, next
            if curr is None:
                return
            next = next or curr
            if prev:
                prev.next = curr
            prev = curr

        node = root
        while node:
            prev = next = None
            while node:
                modify(node.left)
                modify(node.right)
                node = node.next
            node = next
        return root

###############


# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
  # @param root, a tree link node
  # @return nothing
  def connect(self, root):
    p = root
    pre = None
    head = None
    while p:
      if p.left:
        if pre:
          pre.next = p.left
        pre = p.left
      if p.right:
        if pre:
          pre.next = p.right
        pre = p.right
      if not head:
        head = p.left or p.right
      if p.next:
        p = p.next
      else:
        p = head
        head = None
        pre = None

117 - Populating Next Right Pointers in Each Node II

Question

Algorithm

DFS

BFS

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

DFS

BFS

Code

All Problems

All Solutions