116. Populating Next Right Pointers in Each Node (Medium)

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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:

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":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

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

Explanation: Given the above perfect 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.

Solutions

1.

class Solution {

    // Solution meets the requirements perfectly.

    public Node connect(Node root) {
        // return null if root empty
        if (root == null) {
            return root;
        }

        // link root.left  to root.right if root.left exists
        if (root.left != null) {
            root.left.next = root.right;
        }

        // link root.right to father's next's left child
        if (root.right != null && root.next != null && root.next.left != null) {
            root.right.next = root.next.left;
        }

        // link root.
        // then visit root.left and connect
        connect(root.left);

        // visit root.right and connect
        connect(root.right);

        return root;
    }
}

2.

class Solution {

    // Solution violates the constraints. Ask for extra memory space.

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

        // used to keep nodes for each level
        Map<Integer, List<Node>> levelMap = new HashMap<>();

        // populate nodes to same level
        populateLayer(root, 0, levelMap);

        // start to link node of each level
        for (Integer k : levelMap.keySet()) {

            // Nodes kept in list are arranged as the order from left to right.
            List<Node> nodes = levelMap.get(k);

            // since rightmost node has no siblings, ignore it.
            for (int i = 0; i < nodes.size() - 1; i++) {
                nodes.get(i).next = nodes.get(i + 1);
            }
        }

        return root;
    }

    private void populateLayer(Node root, int level, Map<Integer, List<Node>> levelMap) {
        if (root == null) {
            return;
        }

        if (!levelMap.containsKey(level)) {
            levelMap.put(level, new ArrayList<>());
        }

        levelMap.get(level).add(root);

        populateLayer(root.left, level + 1, levelMap);
        populateLayer(root.right, level + 1, levelMap);
    }
}

Incorrect Solutions

class Solution {

    // Incorrect solution

    public Node connect(Node root) {
        // return null if root empty
        if (root == null) {
            return root;
        }

        // link left child to right child if left child exists
        if (root.left != null) {
            root.left.next = root.right;
        }

        // then visit root.left and connect
        connect(root.left);

        // visit root.right and connect
        connect(root.right);

        return root;
    }
}

References