题目大意：
填充每个节点的下一个右侧节点指针
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
输入: root = [1,2,3,4,5,6,7] 输出: [1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=116
解题思路分析：
之前的文章多次提到过，看到二叉树问题，多数要考虑使用dfs或者bfs来解题，本题又是一道这样的题目，这里我们介绍dfs和bfs两种解法来解题。
解法一：dfs深度优先搜索
题目要求将树中的每一个节点与其处于同层的右侧相邻节点连接，那么毫无疑问，当前节点的左子节点应该指向其右子节点，而右子节点则应该指向当前节点相邻右侧节点的左子节点。用上面题目的例子来说明，如果当前节点是2，他的左子节点4应该指向他的右子节点5，而右子节点5应该指向当前节点2的右侧节点3的左子节点6。即：
node.left.next = node.right node.right.next = node.next.left
实现代码：
public Node connect(Node root) {
dfs(root); // dfs每个节点
return root; // 返回root
}
void dfs(Node current){
// 如果当前节点为空，或者当前节点是叶子节点，返回
if(current==null||current.left==null) return;
// 当前节点的左子节点指向其右子节点
current.left.next=current.right;
// 如果当前节点的next不为空
// 当前节点的右子节点指向当前节点next的左子节点
if(current.next!=null) current.right.next=current.next.left;
// 递归左子节点
dfs(current.left);
// 递归右子节点
dfs(current.right);
}本解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node.
Memory Usage: 50.2 MB, less than 6.35% of Java online submissions for Populating Next Right Pointers in Each Node.
解法二：bfs广度优先搜索
bfs的特性在于能够一行一行的遍历二叉树，每遍历出一行节点，我们按顺序将其一一相连即可。
实现代码：
public Node connect(Node root) {
// 根节点为空，返回空
if(root==null) return null;
// bfs用的queue
Queue<Node> q = new LinkedList<>();
// 将根节点加入Queue
q.offer(root);
// bfs遍历每一个点
while(q.size()>0){
// 当前Queue的元素个数
int size = q.size();
// 当前节点左侧节点，默认为空
Node left=null;
// 循环二叉树每一行
while(size>0){
// 取出一个节点
Node n = q.poll();
// 当前行节点数减一
size--;
// 如果左侧节点不为空，将左侧节点的next指向当前节点
if(left!=null) left.next=n;
// 将当前节点更新为左侧节点
left=n;
// 如果存在子节点，将子节点加入Queue
if(n.left!=null){
q.offer(n.left);
q.offer(n.right);
}
} // 当前行遍历结束
}
return root;
}本解法执行时间为6ms。
Runtime: 6 ms, faster than 6.60% of Java online submissions for Populating Next Right Pointers in Each Node.
Memory Usage: 49.6 MB, less than 6.35% of Java online submissions for Populating Next Right Pointers in Each Node.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-116-populating-next-right-pointers-in-each-node-解题思路分析/