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

给定一个二叉树

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

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

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

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }

    stack := list.New() // bfs 的 stack
    stack.PushBack(root)

    for stack.Len() != 0 {
        stackLen := stack.Len()
        for i := 0; i < stackLen; i++ {
            p := stack.Remove(stack.Front()).(*Node) // 先进先出
            if i != stackLen-1 {
                p.Next = stack.Front().Value.(*Node)
            }
            if p.Left != nil {
                stack.PushBack(p.Left)
            }
            if p.Right != nil {
                stack.PushBack(p.Right)
            }
        }
    }
    return root
}

层序遍历即可，参考102题。每一层内把Next指针指向下一个。