? 二叉樹(shù)的遍歷治唤，無(wú)論是在leetcode刷題或者面試過(guò)程中，都是十分常見(jiàn)，重要性無(wú)需贅述处窥。本文將采用Golang語(yǔ)言來(lái)實(shí)現(xiàn)前/中/后/層四種遍歷方式。
二叉樹(shù)定義
// 二叉樹(shù)節(jié)點(diǎn)定義
type TreeNode struct {
Val int
Left *TreeNode // 左子樹(shù)
Right *TreeNode // 右子樹(shù)
}
二叉樹(shù)樣例
一. 前序遍歷
- 遍歷順序
? 中 -> 左 -> 右玄组。
- 遍歷順序
- 代碼實(shí)現(xiàn)
// 前序遍歷
func PreOrderTraversal(tree *TreeNode) {
if tree == nil {
return
}
fmt.Printf(" %d -> ", tree.Val)
PreOrderTraversal(tree.Left)
PreOrderTraversal(tree.Right)
}
- 結(jié)果輸出
1 -> 2 -> 4 -> 3 -> 5 -> 6 ->
- 結(jié)果輸出
二. 中序遍歷
- 遍歷順序
? 左 -> 中 -> 右滔驾。
- 遍歷順序
- 代碼實(shí)現(xiàn)
// 中序遍歷
func MidOrderTraversal(tree *TreeNode) {
if tree == nil {
return
}
MidOrderTraversal(tree.Left)
fmt.Printf(" %d -> ", tree.Val)
MidOrderTraversal(tree.Right)
}
- 結(jié)果輸出
4 -> 2 -> 1 -> 5 -> 3 -> 6 ->
- 結(jié)果輸出
三. 后序遍歷
- 遍歷順序
? 左 -> 右 -> 中。
- 遍歷順序
- 代碼實(shí)現(xiàn)
// 后序遍歷
func PostOrderTraversal(tree *TreeNode) {
if tree == nil {
return
}
PostOrderTraversal(tree.Left)
PostOrderTraversal(tree.Right)
fmt.Printf(" %d -> ", tree.Val)
}
- 結(jié)果輸出
4 -> 2 -> 5 -> 6 -> 3 -> 1 ->
- 結(jié)果輸出
四. 按層遍歷
- 遍歷順序
? 層俄讹。
- 遍歷順序
- 代碼實(shí)現(xiàn)
// 按層遍歷
func LevelOrderTraversal(tree *TreeNode) {
if tree == nil {
return
}
// 采用隊(duì)列實(shí)現(xiàn)
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)
}
}
}
- 結(jié)果輸出
1 -> 2 -> 3 -> 4 -> 5 -> 6 ->
- 結(jié)果輸出
