Question_116.md

LeetCode Records - Question 116 Populating Next Right Pointers in Each Node

Attempt 1: Use an ArrayList to save the next level of nodes

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

        List<Node> prevNodes = new ArrayList<>();
        prevNodes.add(root);
        
        while (!prevNodes.isEmpty()) {
            List<Node> nodes = new ArrayList<>();

            int size = prevNodes.size();
            Node curr = prevNodes.get(0);
            for (int i = 0; i < size - 1; i++) {
                Node next = prevNodes.get(i + 1);

                curr.next = next;
                if (curr.left != null) {
                    nodes.add(curr.left);
                }
                if (curr.right != null) {
                    nodes.add(curr.right);
                }

                curr = next;
            }
            curr.next = null;
            if (curr.left != null) {
                nodes.add(curr.left);
            }
            if (curr.right != null) {
                nodes.add(curr.right);
            }
            
            prevNodes = nodes;
        }

        return root;
    }
}

• Runtime: 2 ms (Beats: 54.94%)
• Memory: 44.12 MB (Beats: 64.98%)