Populating Next Right Pointers in Each Node

1package pkg5leetcode.interview150;2 3/*4 * Populating Next Right Pointers in Each Node | LC 1165 * APPROACH: Level-order connect siblings using previously established links.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC116PopulatingNextRightPointers {9    static class Node {10        int val;11        Node left, right, next;12        Node(int val) { this.val = val; }13    }14 15    static Node connect(Node root) {16        if (root == null) return null;17        Node leftmost = root;18        while (leftmost.left != null) {19            Node head = leftmost;20            while (head != null) {21                head.left.next = head.right;22                if (head.next != null) head.right.next = head.next.left;23                head = head.next;24            }25            leftmost = leftmost.left;26        }27        return root;28    }29 30    public static void main(String[] args) {31        Node root = new Node(1);32        root.left = new Node(2);33        root.right = new Node(3);34        root.left.left = new Node(4);35        root.left.right = new Node(5);36        root.right.left = new Node(6);37        root.right.right = new Node(7);38        connect(root);39        check(root.next == null && root.left.next == root.right, "case1");40        check(root.left.left.next == root.left.right, "case2");41        System.out.println("all tests passed");42    }43 44    static void check(boolean cond, String name) {45        if (!cond) throw new AssertionError("FAILED: " + name);46        System.out.println("  PASS " + name);47    }48}