Populating Next Right Pointers in Each Node

Question

Given a binary tree. 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.

Solution

這題很直觀的會想到用 level order traversal，只是效率比較差一些。可以善用題目所給的 "initially, all next pointers are set to NULL"

public void connect(TreeLinkNode root) {
    if(root == null)
        return;

    if(root.left != null){
        root.left.next = root.right;
        if(root.next != null)
            root.right.next = root.next.left;
    }

    connect(root.left);
    connect(root.right);
}