Populating Next Right Pointers in Each Node II

Question

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

Solution

一樣用九章的 level order traversal 可以直接解。但解答的解法是用新建一個 dummy，然後透過 dummy 來進行 level order traversal，當走到該 level 的最後一個時，再把 dummy 設為下一個 level 的開頭

public void connect(TreeLinkNode root) {
    TreeLinkNode dummyHead = new TreeLinkNode(0);
    TreeLinkNode pre = dummyHead;
    while (root != null) {
        if (root.left != null) {
            pre.next = root.left;
            pre = pre.next;
        }
        if (root.right != null) {
            pre.next = root.right;
            pre = pre.next;
        }
        root = root.next;
        if (root == null) {
            pre = dummyHead;
            root = dummyHead.next;
            dummyHead.next = null;
        }
    }
}