二叉树的遍历，无论是在leetcode刷题或者面试过程中，都是十分常见，重要性无需赘述。本文将采用Golang语言来实现前/中/后/层四种遍历方式。
二叉树定义
// 二叉树节点定义
type TreeNode struct {
Val int
Left *TreeNode // 左子树
Right *TreeNode // 右子树
}
二叉树样例
一. 前序遍历
- 遍历顺序
中 -> 左 -> 右。
- 遍历顺序
- 代码实现
// 前序遍历
func PreOrderTraversal(tree *TreeNode) {
if tree == nil {
return
}
fmt.Printf(" %d -> ", tree.Val)
PreOrderTraversal(tree.Left)
PreOrderTraversal(tree.Right)
}
- 结果输出
1 -> 2 -> 4 -> 3 -> 5 -> 6 ->
- 结果输出
二. 中序遍历
- 遍历顺序
左 -> 中 -> 右。
- 遍历顺序
- 代码实现
// 中序遍历
func MidOrderTraversal(tree *TreeNode) {
if tree == nil {
return
}
MidOrderTraversal(tree.Left)
fmt.Printf(" %d -> ", tree.Val)
MidOrderTraversal(tree.Right)
}
- 结果输出
4 -> 2 -> 1 -> 5 -> 3 -> 6 ->
- 结果输出
三. 后序遍历
- 遍历顺序
左 -> 右 -> 中。
- 遍历顺序
- 代码实现
// 后序遍历
func PostOrderTraversal(tree *TreeNode) {
if tree == nil {
return
}
PostOrderTraversal(tree.Left)
PostOrderTraversal(tree.Right)
fmt.Printf(" %d -> ", tree.Val)
}
- 结果输出
4 -> 2 -> 5 -> 6 -> 3 -> 1 ->
- 结果输出
四. 按层遍历
- 遍历顺序
层。
- 遍历顺序
- 代码实现
// 按层遍历
func LevelOrderTraversal(tree *TreeNode) {
if tree == nil {
return
}
// 采用队列实现
queue := make([]*TreeNode, 0)
queue = append(queue, tree) // queue push
for len(queue) > 0 {
tree = queue[0]
fmt.Printf(" %d -> ", tree.Val)
queue = queue[1:] // queue pop
if tree.Left != nil {
queue = append(queue, tree.Left)
}
if tree.Right != nil {
queue = append(queue, tree.Right)
}
}
}
- 结果输出
1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
- 结果输出
