116. Populating next right point

这道题实际上就是要你能够分别出用什么方法来解决。

用什么算法

这道题其实挺明显使用level order traversal来做的，但是我一开始居然还想着用divide and conquer。
它实际上在默认设置中node.next 就是null所以你在循环的时候只需要把队列里面的node.next设置好就行了，最后一个根本不用管。其实没有这个default设置你也只需要再加一个判断条件就可以了。就是当前指针如果在队列最后一个element，直接把node.next指到null就可以了。

这道题8月底的时候做过，没想到过两个月就忘了。还是需要多加练习。因为你还是对数据结构理解不够深刻，不知道这道题实际上用level order traversal就可以直接解决。
下面是代码，实际上就是再练习了一遍queue的用法……

    public Node connect(Node root) {
        if (root == null) return root;
        Queue<Node> queue = new LinkedList<>();
        Node res = root;
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                if (i < size - 1) {
                    cur.next = queue.peek();
                }
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
        }
        return res;
    }

时空复杂度

Time O（N）
Space O（N）
空间复杂度可以优化。后面可以学习一下