层序遍历

树

说明

借助队列逐层访问节点；时间 O(n)。

分析

队列先装入根节点，每取出一个节点就把它的孩子按顺序放到队尾。这样可以保证所有同层节点先于下一层被处理。

以根2、左1、右3为例，访问顺序为2,1,3。先把根入队，取出根后将左、右孩子入队；分层时先固定本层节点数。每个节点访问一次；递归栈随树高变化，层序队列峰值则受层宽影响。

查看图表代码

适用前提与边界

若要按层分组，可以在每轮记录当前队列长度，再处理恰好这些节点。 空根返回nil切片；队列空间可能达到O(n)，实际峰值由树的层宽决定。

示例输入与调用

root := &Node{Value: 2, Left: &Node{Value: 1}, Right: &Node{Value: 3}}
	fmt.Println(LevelOrder(root))

运行输出

[2 1 3]

完整 Go 示例

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func LevelOrder(root *Node) []int {
	if root == nil {
		return nil
	}
	q := []*Node{root}
	out := []int{}
	for len(q) > 0 {
		n := q[0]
		q = q[1:]
		out = append(out, n.Value)
		if n.Left != nil {
			q = append(q, n.Left)
		}
		if n.Right != nil {
			q = append(q, n.Right)
		}
	}
	return out
}

func main() {
	root := &Node{Value: 2, Left: &Node{Value: 1}, Right: &Node{Value: 3}}
	fmt.Println(LevelOrder(root))
}