填充每个节点的下一个右侧节点指针

---

LeetCode 116

https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

解题思路

BFS层序遍历

题意是让我们把二叉树的每一层从左到右都连接成一个链表，所以很好想到直接使用BFS对二叉树进行层序遍历。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
public class Solution {
    public Node connect(Node root) {
        if (root == null) return null;

        Deque<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node curNode = queue.poll();
                // 出队，如果不是该层最右边的节点，则与队首元素（即右侧节点）连接
                if (i < size - 1) {
                    curNode.next = queue.peek();
                }
                // 因为该二叉树是完美二叉树，所以只要有左孩子，必有右孩子，无需再判断是否有右孩子
                if (curNode.left != null) {
                    queue.add(curNode.left);
                    queue.add(curNode.right);
                }
            }
        }
        return root;
    }
}  

但考虑到题目最后面说，要使用常数级的空间复杂度算法，所以有了如下解法。

---

递归

因为当前一层的节点，可通过next指针将该层节点全部串在一起，所以可以直接操作下一层的节点也串在一起。

如果存在左孩子，则直接与其右孩子串在一起

接下来，判断当前节点是否为该层最右侧节点 root.next != null

不是最右侧，则当前节点的右孩子也要连上右边的节点。 root.right.next = root.next.left

然后递归遍历下去，这里注意，如果是该层最右侧节点，则什么都不做，因为题目默认next指针为null，已操作过。

public class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        connection(root);
        return root;
    }

    public void connection(Node root) {
        if (root.left == null) return;  // 已经到达叶子结点
        root.left.next = root.right;
        // 当前节点不是在该层的最右侧节点，则继续将节点连在一起
        // 如果是最右侧节点，则不作处理，题目说了默认next = null，已经处理过了
        if (root.next != null) {
            root.right.next = root.next.left;
        }
        connection(root.left);
        connection(root.right);
    }
}