LeetCode220726_50、填充每个节点的下一个右侧节点指针

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

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

图1 填充每个节点的下一个右侧节点指针

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解一、迭代解法，当root为空，返回，不为空时，第一层不用连，第二层左右节点相连，第三层，左右节点连后，通过上一层连接关系进行cur.right.next = cur.next.left，后面层类似。

class Solution{
    public Node connect(Node root){
        if(root == null){
            return root;
        }
        Node pre = root;
        while(pre.left != null){
                Node cur = pre;
                while(cur != null){
                cur.left.next = cur.right;
                if(cur.next != null){
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
                
            }
            pre = pre.left;
        }
        return root;
    }
 
}

题解二、递归解法，终止条件，为空，返回。从根节点，纵向连接，左节点的next为右节点，左节点等于左节点的右节点，右节点等于右节点的左节点，直至为空，说明遍历至底层，递归左子节点，右子节点。

详解见链接内题解三

动画演示+三种实现 116. 填充每个节点的下一个右侧节点指针 - 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

class Solution{
    public Node connect(Node root){
        dfs(root);
        return root;
    }
    public void dfs(Node root){
        if(root == null){
            return;
        }    
        Node left = root.left;
        Node right = root.right;
        while(left != null){
            left.next = right;
            left = left.right;
            right = right.left;
        }
        dfs(root.left);
        dfs(root.right);
    }
}