Populating Next Right Pointers in Each Node I & II

I : Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *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.
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

可以用一个queue做BFS，但是此题要求Space: O(n)。因为这个是个完全树，所以当前左子树的下一个肯定是当前右子树，当前右子树肯定是当前下一个的左子树。注意Null check。

public class Solution {
    //Time: O(n)  Space: O(logn)
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            root.left.next = root.right;   
        }
        if (root.right != null) {
            root.right.next = root.next == null ? null : root.next.left;   
        }
        connect(root.left);
        connect(root.right);
    }
}

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?

比上一题复杂不少，但是基本思路还是一样的。当前点有两个子树时，关键在于右子树的下一个，当前点只有一个子树时，关键在于这个子树对应的下一个。

首先要坚持当前点是否有下一个，如果有在检查下一个点是否有左右子树，把之前的那个子树对应到现在的的子树。递归对整棵树求解，需要注意的是先对右子树递归。

public class Solution {
    //Time: O(n)  
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        TreeLinkNode p = null;
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
            p = root.right;
        } else if (root.left != null || root.right != null) {
            p = root.left != null ? root.left : root.right;
        } else {
            return;
        }
        TreeLinkNode p2 = root;
        while (p2.next != null && p2.next.left == null && p2.next.right == null) {
            p2 = p2.next;
        }
        p.next = p2.next == null ? null : (p2.next.left != null ? p2.next.left : p2.next.right);
        connect(root.right);
        connect(root.left);
    }
}