117. Populating Next Right Pointers in Each Node II - jiejackyzhang/leetcode-note GitHub Wiki

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?

Note:

• You may only use constant extra space.

For example,

Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

解题思路为一层一层来连接。 技巧为设置一个dummy node作为每一层的head，然后用一个prev指针指向前面一个node，实现next连接。 若root.next为null时，说明这一层已到最后，可以对下一层继续，重新设置dummy和prev。

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode dummy = new TreeLinkNode(0);
        TreeLinkNode prev = dummy;
        while(root != null) {
            if(root.left != null) {
                prev.next = root.left;
                prev = prev.next;
            }
            if(root.right != null) {
                prev.next = root.right;
                prev = prev.next;
            }
            root = root.next;
            if(root == null) {
                // go to next level
                root = dummy.next;
                dummy.next = null;
                prev = dummy;
            }
        }
    }
}