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

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

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

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

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

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

方法一：层次遍历

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

方法二：使用已建立的next指针
第一种 是这两个串联的节点都有一个共同的父节点，通过父节点就可以将这两个子节点串联起来

第二种 是这两个串联的节点的父节点不同，对于这种情况，如果我们能将这一层的上一层串联好。那么可以通过父节点的next找到邻居，完成串联。

也就是说当我们要串联第 i 层节点时，需要先完成第 i-1 层的节点串联
第一层最多只有一个节点，不需要串联
第二层最多只有两个节点，借助根节点就可以完成串联了
第三层串联时，上一层已经串联完了，所以第三层可以完成串联
同理，可以完成第四层，第五层，第N层的串联

public Node connect(Node root) {
    if (root == null) {
        return root;
    }
    Node head = root;
    while (head.left != null) {
        Node p = head;
        while (p != null) {
            p.left.next = p.right;
            if (p.next != null) {
                p.right.next = p.next.left;
            }
            p = p.next;
        }
        head = head.left;    
    }
    return root;
}

方法三：递归

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

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

给定一个二叉树：

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

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

示例 1

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

使用已建立的 next 指针

• 从第一层开始（第一层只有一个 root 节点），每次循环遍历当前层的链表节点，通过节点的 left 和 right 得到下一层的节点。
• 把下一层的节点从左到右连接成一个链表。
• 拿到下一层链表的头节点，进入下一轮循环。

代码实现时，可以用一个哨兵节点来表示「第一个节点之前的节点」，从而减少一些关于空节点的判断逻辑。

public Node connect(Node root) {
    if (root == null) {
        return root;
    }
    Node dummy = new Node();
    Node p = root;
    while (p != null) {
        Node q = dummy;
        while (p != null) {
            if (p.left != null) {
                q.next = p.left;
                q = q.next;
            }
            if (p.right != null) {
                q.next = p.right;
                q = q.next;
            }
            p = p.next;
        }
        p = dummy.next;
        dummy.next = null;
    }
    return root;
}

递归
DFS 这棵树，从根节点 1 出发，向左递归到 2，再向左递归到 4。
这三个节点正好是每一层的第一个节点（类似链表头），用一个数组 pre 记录，即 pre[0] 为节点 1，pre[1] 为节点 2，pre[2] 为节点 4。pre的下标就是节点的深度。
继续递归到 5（深度为 2），从 pre[2] 中拿到节点 4，把 4 的 next 指向 5。然后更新 pre[2] 为节点 5，这样在后面递归到节点 7 时，就可以从 pre[2] 中拿到节点 5，把 5 的 next 指向 7 了。

private List<Node> pre = new ArrayList<>();

public Node connect(Node root) {
    dfs(root, 0);
    return root;
}

private void dfs(Node root, int level) {
    if (root == null) {
        return;
    }
    if (level == pre.size()) {
        pre.add(root);
    } else {
        pre.get(level).next = root;
        pre.set(level, root);
    }
    dfs(root.left, level + 1);
    dfs(root.right, level + 1);
}