一、题目描述：
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
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
进阶：
你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
来源：力扣（LeetCode） 题目链接：leetcode-cn.com/problems/po…
二、思路分析：
分类讨论，由示意图可以看出，对于结点root来说，root的左孩子指向root的右孩子，而root的右孩子指向root的next的左孩子。
那么从root开始，对于每一个节点，存在如下关系
自己的左子节点的Next应该为自己的右子节点 自己的右子节点的Next应该为自己的Next的左子节点 当从顶向下，从左向右遍历时，Root的Next确定为Nil
三、AC 代码：
class Solution { public Node connect(Node root) { trav(root); trav2(root); return root; } private void trav(Node root) { if(root==null) return; if(root.left!=null) root.left.next=root.right; trav(root.left); trav(root.right); } private void trav2(Node root) { if(root==null) return; if(root.right!=null) { if(root.next==null) root.right.next=null; else root.right.next=root.next.left; } trav2(root.left); trav2(root.right); } }
四、总结：
写题解不易，若对你有帮助，点赞评论再走吧。ヽ(✿ﾟ▽ﾟ)ノ，如有不足，请大家斧正。
