题目链接：https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/

1. 题目介绍（）

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

【Translate】： 给你一个完美的二叉树，所有的叶结点都在同一层，每个父结点都有两个子结点。二叉树的定义如下：

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

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

【Translate】： 填充每个next指针，使其指向它右边的下一个节点。如果没有下一个右节点，则下一个指针应设置为NULL。

Initially, all next pointers are set to NULL.

【Translate】： 最初，所有的next指针都被设置为NULL。

【测试用例】：

示例1：

示例2：

【条件约束】：

【跟踪】：

Follow-up:

• You may only use constant extra space.
• The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.

【Translate】：

• 只使用常数的额外空间。
• 递归方法很好。对于这个问题，您可以假设隐式堆栈空间不算作额外空间。

【相似问题】：

2. 题解

2.1 层序遍历

该题解是在 【LeetCode】No.102. Binary Tree Level Order Traversal – Java Version 的基础上，稍作修改得到的，通过Queue来实现BFS，保证queue每次只存储当前层元素，当前元素通过弹出获得，next元素查询但不弹出，直到最后元素后，让其next为null.

/*
// 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 null;Queue queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){int qlen = queue.size();for(int i = 0; i < qlen; i++){Node curr = queue.poll();Node second = queue.peek();curr.next = second;if(i == qlen-1){curr.next = null;}if(curr.left != null) queue.add(curr.left);if(curr.right != null) queue.add(curr.right);}}return root;}
}

2.2 递归

原题解来自于 wilsoncursino 的 Java 0ms with visual explanation.

不得不说，这确实是一个很巧妙的办法，对代码有疑惑的同学看一下上面的图应该就能很容易理清思路了。

/*
// 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 null;if(root.left != null) root.left.next = root.right;if(root.right != null && root.next != null) root.right.next = root.next.left;connect(root.left);connect(root.right);return root;}
}