二叉树 前/中/后/层 四种方式遍历递归实现

二叉树的遍历,无论是在leetcode刷题或者面试过程中,都是十分常见,重要性无需赘述。本文将采用Golang语言来实现前/中/后/层四种遍历方式。

二叉树定义

// 二叉树节点定义
type TreeNode struct {
 Val int
 Left *TreeNode // 左子树
 Right *TreeNode // 右子树
}

二叉树样例

一. 前序遍历

• 1. 遍历顺序
     中 -> 左 -> 右。
• 2. 代码实现

// 前序遍历
func PreOrderTraversal(tree *TreeNode) {
 if tree == nil {
 return
 }
 fmt.Printf(" %d -> ", tree.Val)
 PreOrderTraversal(tree.Left)
 PreOrderTraversal(tree.Right)
}

• 3. 结果输出
     1 -> 2 -> 4 -> 3 -> 5 -> 6 ->

二. 中序遍历

• 1. 遍历顺序
     左 -> 中 -> 右。
• 2. 代码实现

// 中序遍历
func MidOrderTraversal(tree *TreeNode) {
 if tree == nil {
 return
 }
 MidOrderTraversal(tree.Left)
 fmt.Printf(" %d -> ", tree.Val)
 MidOrderTraversal(tree.Right)
}

• 3. 结果输出
     4 -> 2 -> 1 -> 5 -> 3 -> 6 ->

三. 后序遍历

• 1. 遍历顺序
     左 -> 右 -> 中。
• 2. 代码实现

// 后序遍历
func PostOrderTraversal(tree *TreeNode) {
 if tree == nil {
 return
 }
 PostOrderTraversal(tree.Left)
 PostOrderTraversal(tree.Right)
 fmt.Printf(" %d -> ", tree.Val)
}

• 3. 结果输出
     4 -> 2 -> 5 -> 6 -> 3 -> 1 ->

四. 按层遍历

• 1. 遍历顺序
     层。
• 2. 代码实现

// 按层遍历
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)
 }
 }
}

• 3. 结果输出
     1 -> 2 -> 3 -> 4 -> 5 -> 6 ->

本文来自:简书

感谢作者:缘木求鱼的鱼

查看原文:二叉树 前/中/后/层 四种方式遍历递归实现

• 编辑
• 预览