【LeetCode】116. 填充每个节点的下一个右侧节点指针

1 问题

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

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 指针连接，’#’ 标志着每一层的结束。

示例 2

输入：root = []
输出：[]

提示

树中节点的数量在[0, 2$^12$ - 1]范围内
-1000 <= node.val <= 1000

进阶

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

2 解题思路

2.1 BFS

在【LeetCode】102.二叉树的层序遍历 一文中，我们可以利用层序遍历，即队列的思想遍历每层节点，当遍历完每层后，再将该层节点连接起来。

2.2 DFS

将Node看成是一个三叉树，利用递归，将某个节点的左右子节点连接，再递归其左右子节点，然后将左节点的右子节点，与右节点的左子节点连接，依次递归即可完成。

3 代码

3.1 DFS

class Solution {
    //use DFS
    public Node connect(Node root) {
        if (root == null)
            return null;
        // 遍历「三叉树」，连接相邻节点
        traverse(root.left, root.right);
        return root;
    }

    // 三叉树遍历框架
    void traverse(Node node1, Node node2) {
        if (node1 == null || node2 == null) {
            return;
        }
        /**** 前序位置 ****/
        // 将传入的两个节点穿起来
        node1.next = node2;

        // 连接相同父节点的两个子节点
        traverse(node1.left, node1.right);
        traverse(node2.left, node2.right);
        // 连接跨越父节点的两个子节点
        traverse(node1.right, node2.left);
    }
}

3.2 BFS

class Solution {
    // use BFS
    public Node connect(Node root) {
        if (null == root) {
            return root;
        }
        Queue<Node> queue = new LinkedList();
        List<Node> rowList = new LinkedList();
        queue.offer(root);
        queue.offer(null);
        Node tmp;
        while (!queue.isEmpty()) {
            tmp = queue.poll();
            if (null != tmp) {
                rowList.add(tmp);
                if (null != tmp.left) {
                    queue.offer(tmp.left);
                }
                if (null != tmp.right) {
                    queue.offer(tmp.right);
                }
            } else if (!rowList.isEmpty()) {
                //linked the next node
                for (int i = 0; i < rowList.size() - 1; i++) {
                    rowList.get(i).next = rowList.get(i + 1);
                }
                rowList.get(rowList.size() - 1).next = null;
                rowList = new ArrayList();
                queue.offer(null);
            }
        }
        return root;
    }
}