填充每个结点的下一个右侧节点

来源Leetcode第116题填充每个结点的下一个右侧节点

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例：

提示：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

---

常规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;
    }
};
*/
class Solution {
    public Node connect(Node root) {
        if(root == null)
            return root;
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(root);
        int size = 0;
        Node tmp;
        while(!queue.isEmpty()){
            size = queue.size();
            tmp = queue.peek();
            for(int i = 1; i < size ; ++i){  //串联队列里的结点
                tmp.next = queue.get(i);
                tmp = queue.get(i);
            }
            for(int i = 0 ; i < size ; ++i){
                tmp = queue.poll();
                if(tmp.left != null)
                    queue.add(tmp.left);
                if(tmp.right != null)
                    queue.add(tmp.right);
            }
        }
        return root;
    }
}

利用已有的next结点

如果不为一层的尾结点，那么其next指针只想的就是根节点的右孩子，或者更结点兄弟的右孩子，根节点的兄弟在上一轮递归中已经用root.next实现了。

public Node connect(Node root) {
 if(root == null){
        return null;
    }
    if(root.left != null){
        root.left.next = root.right;
    }
    if(root.right != null){
        root.right.next = root.next == null ? null : root.next.left;
    }
    connect(root.left);
    connect(root.right);
    return root;
}