LeetCode_21_PopulatingNextRightPointersInEachNode

1. question: 填充每个节点的下一个右侧节点（中等）

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

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, 212 - 1] 范围内
-1000 <= node.val <= 1000

2. answers

这道题和前序遍历一样，需要在遍历的时候，将指针指向下一个节点即可。代码如下所示：（其实无论是不是完全二叉树，没关系的，都是层序遍历。）

public class Nodes {

    public int val;
    public Nodes left;
    public Nodes right;
    public Nodes next;

    public Nodes() {}

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

    public Nodes(int _val, Nodes _left, Nodes _right, Nodes _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

public class Solution_0019 {

    public static Nodes connect(Nodes root) {

        if(root == null) {
            return null;
        }

        Queue<Nodes> queue = new LinkedList<>();

        queue.offer(root);

        int length;

        while(!queue.isEmpty()) {
            length = queue.size();

            // 空节点
            Nodes nodes = new Nodes();

            while(length > 0) {
                nodes.next = queue.poll();
                nodes = nodes.next;
                length --;

                if(nodes.left != null) {
                    queue.offer(nodes.left);
                }

                if(nodes.right != null) {
                    queue.offer(nodes.right);
                }
            }

            // 注意，最后一个节点的next设为null
            nodes.next = null;
        }

        return root;
    }

    public static void main(String[] args) {
        Nodes n1 = new Nodes(4);
        Nodes n2 = new Nodes(5);
        Nodes n3 = new Nodes(2, n1, n2, null);

        Nodes n4 = new Nodes(6);
        Nodes n5 = new Nodes(7);
        Nodes n6 = new Nodes(3, n4, n5, null);

        Nodes root = new Nodes(1, n3, n6, null);

        root = connect(root);

        // 先序遍历输出
        Queue<Nodes> queue = new LinkedList<>();
        queue.offer(root);
        int length;

        while(!queue.isEmpty()) {

            length = queue.size();

            while(length > 0) {

                root = queue.poll();
                System.out.print(root.val);
                System.out.print("{");
                System.out.print(root.next);
                System.out.print("}");
                System.out.println();

                if(root.left != null) {
                    queue.offer(root.left);
                }

                if(root.right != null) {
                    queue.offer(root.right);
                }

                length --;
            }
        }
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。