116.填充每个节点的下一个右侧节点指针

解法一：递归
解法三：DFS-非递归
解法四：DFS-递归

[tree](https://leetcode.com/tag/tree) | [depth-first-search](https://leetcode.com/tag/depth-first-search)
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

进阶：

你只能使用常量级额外空间。

使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：
116.填充每个节点的下一个右侧节点指针 - 图1

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

提示：

树中节点的数量少于 4096
-1000 <= node.val <= 1000

解法一：递归

为了完成 5->6 的连接，所以我们需要借助函数参数来解决 ```go func connect(root Node) Node { if root == nil {
```
  return root
```
} connectTwoNode(root.Left, root.Right)

return root }

func connectTwoNode(left Node, right Node) { if left == nil || right == nil { return } left.Next = right connectTwoNode(left.Left, left.Right) connectTwoNode(right.Left, right.Right) connectTwoNode(left.Right, right.Left) }


<a name="Br3I0"></a>
## 解法二：BFS
```go
func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    // 使用队列来模拟，先进先出
    queue := []*Node{}
    queue = append(queue, root)
    for len(queue) > 0 {
        size := len(queue)
        temp := queue[0]
        // 串联起来
        for i := 1; i < size; i++ {
            temp.Next = queue[i]
            temp = temp.Next
        }
        for i := 0; i < size; i++ {
            // 不能这么用，会导致 queue 也是一个新的变量
            // temp, queue := queue[0], queue[1:]
            var temp *Node
            temp, queue = queue[0], queue[1:]
            if temp.Left != nil {
                queue = append(queue, temp.Left)
            }
            if temp.Right != nil {
                queue = append(queue, temp.Right)
            }
        }
    }
    return root
}

解法三：DFS-非递归

func connect(root *Node) *Node {
    // 使用 栈 完成 DFS
    var stack = []*Node{}
    stack = append(stack, root)
    for len(stack) > 0 {
        var top *Node
        top, stack = stack[len(stack)-1], stack[:len(stack)-1]
        if top.Left != nil {
            top.Left.Next = top.Right
        }
        // 连接左树的右节点和右树的左节点
        // 同时存在右节点和 Next 指针
        if root.Right != nil && root.Next != nil  {
            top.Right.Next = top.Next.Left
        }
        if top.Right != nil {
            stack = append(stack, top.Right)
        }
        if top.Left != nil {
            stack = append(stack, top.Left)
        }
    }
    return root
}

解法四：DFS-递归

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    if root.Left != nil {
        root.Left.Next = root.Right
    }
    if root.Right != nil && root.Next != nil {
        root.Right.Next = root.Next.Left
    }
    connect(root.Left)
    connect(root.Right)
    return root
}

解法一：递归

解法三：DFS-非递归

解法四：DFS-递归