Level Order 遍历

Populating Next Right Pointers in Each Node

本质上是一个BFS的问题，利用上一层已经连接好的next指针作为一个queue来使用。可以在O(1)的时间和O(n)的空间来解决。

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

        TreeLinkNode cur = root, nextLevel = null;

        while(cur.left != null) {
            nextLevel = cur.left;
            while(cur != null) {
                // 因为是完全二叉树，所以可以一个loop里面连接两次
                cur.left.next = cur.right;

                if(cur.next == null) {
                    cur.right.next = null;
                } else {
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }
            cur = nextLevel;
        }
    }
}

Populating Next Right Pointers in Each Node II

这一题出现了几个问题：

• 中间有空缺节点的话，怎么让上层找到“下一个”正确的节点
• 如果某一层最左边有空缺的话，如何在进入下一层的时候找到正确的起点。(dummy node)

这一题的本质是：我们要做的其实是 level order 建一个 LinkedList（Queue） 出来。

public class Solution {
    public void connect(TreeLinkNode root) {
        while(root != null) {
            TreeLinkNode dummy = new TreeLinkNode(0);
            TreeLinkNode cur = dummy;
            for(; root != null; root = root.next) {
                if(root.left != null) {
                    cur.next = root.left;
                    cur = cur.next;
                }
                if(root.right != null) {
                    cur.next = root.right;
                    cur = cur.next;
                }
            }
            root = dummy.next;
        }
    }
}