填充每个节点的下一个右侧节点指针。给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。进阶：你只能使用常量级额外空间。使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。力扣116。
层次遍历。双端队列，利用现成的node的next指针。
时间复杂度：O(N)。
额外空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
head := &Node{}
head.val = 3
head.left = &Node{}
head.left.val = 9
head.right = &Node{}
head.right.val = 20
head.right.left = &Node{}
head.right.left.val = 15
head.right.right = &Node{}
head.right.right.val = 7
connect(head)
fmt.Println(head.left.next)
}
// 不要提交这个类
type Node struct {
val int
left *Node
right *Node
next *Node
}
// 提交下面的代码
func connect(root *Node) *Node {
if root == nil {
return root
}
queue := &MyQueue{}
queue.offer(root)
for !queue.isEmpty() {
// 第一个弹出的节点
var pre = &Node{}
size := queue.size
for i := 0; i < size; i++ {
cur := queue.poll()
if cur.left != nil {
queue.offer(cur.left)
}
if cur.right != nil {
queue.offer(cur.right)
}
if pre != nil {
pre.next = cur
}
pre = cur
}
}
return root
}
type MyQueue struct {
head *Node
tail *Node
size int
}
func (this *MyQueue) isEmpty() bool {
return this.size == 0
}
func (this *MyQueue) offer(cur *Node) {
this.size++
if this.head == nil {
this.head = cur
this.tail = cur
} else {
this.tail.next = cur
this.tail = cur
}
}
func (this *MyQueue) poll() *Node {
this.size--
ans := this.head
this.head = this.head.next
ans.next = nil
return ans
}执行结果如下：
