一道特殊的二叉树BFS题目。

1. 题目

给定一个二叉树

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

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

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

进阶：

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

2. 解法

现在网上的解法是适用于完全二叉树（原题是完全二叉树）的，但是对于普通二叉树，就不实用了。把握住两个点：

1. 利用next节点可以在二叉树的同一级内自由跳转。
2. 需要找到同一级内离你最近的右侧节点。

很明显可以用BFS来做，将代码修改一下加一个BFS逻辑就可以了（不是典型BFS代码的样式，没有队列，但是思想是BFS，分层遍历）。

1. 利用next节点从左向右遍历当前节点的层次，帮当前节点的下一层节点找到他们的next节点。
2. 用一个变量记下下一个节点的最左节点。
3. 再遍历下一层，循环往复。

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */

func connect(root *Node) *Node {
    if root == nil {
        return root
    }   
    
    for leftNode:= root;leftNode!=nil;{
        var firstChild *Node
        for curNode := leftNode;curNode != nil;curNode = curNode.Next{
            if curNode.Left != nil{
                if curNode.Right != nil{
                    curNode.Left.Next=curNode.Right;
                }else if curNode.Next != nil {
                    curNode.Left.Next=findLeftestNode(curNode.Next)
                }
                if firstChild == nil{
                    firstChild = curNode.Left
                }
            }
            if curNode.Right != nil {
                if curNode.Next != nil{ 
                    curNode.Right.Next = findLeftestNode(curNode.Next)
                }
                if firstChild == nil{
                    firstChild = curNode.Right
                }
            }
        }
        leftNode = firstChild
    }

	return root
}

func findLeftestNode(root *Node) *Node{
    for curNode:= root; curNode != nil ;curNode = curNode.Next{
        if curNode.Left != nil{
            return curNode.Left
        }
        if curNode.Right != nil{
            return curNode.Right
        }
    }
    return nil
}