ORID54 BFS

117. Populating Next Right Pointers in Each Node II 解题报告

算法

这道题虽然在DFS这个标签里，而且跟之前Populating Next Right Pointers in Each Node 这道题很像，但是这道题用BFS做更合适，因为之前那道题有前提条件，那就是这个BST是个完美的BST，左右平衡。所以recursion可以用backtracking（每个叶子节点都做一遍）来做。
这道题的前提条件就是这颗二叉树不会左右平衡了，所以你需要考虑如果左边叶子节点想要连接到右边的叶子结点的时候，如果右边叶子结点不存在怎么办。这时候实际上BFS能更轻松的解决这个问题。
因为BFS实际上是level order traversal，你可以逐层遍历，那么你所需要的只是把每一层的节点从左到右连接起来。这样无论有一个叶子节点是否缺少，你都只需要把这一层的节点来连接起来就好了……
为什么用这个算法？
BFS能更轻松的解决这个问题。

代码实现

有什么要注意的地方？
其实这道题解决的精髓还是在把问题想清楚这个方面上。如果你能够看清这道问题本质上是level order traversal，那么你就清楚的想到了用BFS来做。问题就迎刃而解了
代码

    public Node connect(Node root) {
        if (root == null) return root;
        Queue<List<Node>> q = new LinkedList<>();
        List<Node> first = new ArrayList<>();
        first.add(root);
        q.add(first);
        while (!q.isEmpty()) {
            List<Node> currentLevel = q.poll();
            int size = currentLevel.size();
            List<Node> nextLevel = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node node = currentLevel.get(i);
                if (i + 1 == size) {
                    node.next = null;
                } else {
                    node.next = currentLevel.get(i+1);
                }                
                if (node.left != null) {
                    nextLevel.add(node.left);
                }
                if (node.right != null) {
                    nextLevel.add(node.right);
                }
            }
            if (nextLevel.size() != 0) {
                q.add(nextLevel);
            }            
        }
        return root;
    }

时间空间复杂度

O(n) (这颗树的总共节点）

哪些相关题目做过的？

目前没想到。