中序遍歷:左節(jié)點(diǎn)(左子樹),中間節(jié)點(diǎn)奢米,右節(jié)點(diǎn)(右子樹)
前序遍歷:中間節(jié)點(diǎn)掏导,左節(jié)點(diǎn)(左子樹)享怀,右節(jié)點(diǎn)(右子樹)
后序遍歷:左節(jié)點(diǎn)(左子樹),右節(jié)點(diǎn)(右子樹)趟咆,中間節(jié)點(diǎn)
層序遍歷:從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)添瓷,每一層遍歷
func Start() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 4,
},
Right: &TreeNode{
Val: 5,
},
},
Right: &TreeNode{
Val: 3,
Left: &TreeNode{
Val: 6,
},
Right: &TreeNode{
Val: 7,
},
},
}
fmt.Println(layer(root))
fmt.Println(layerLoop(root))
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 層序遍歷的迭代
func layerLoop(root *TreeNode) [][]int {
var res [][]int
stackData := list.New()
index := 0
if root != nil {
stackData.PushBack(root)
}
// 當(dāng)隊(duì)列中數(shù)據(jù)為空的時(shí)候程序退出
for stackData.Len() > 0 {
// 新隊(duì)列
stackData1 := list.New()
var tmpRet []int
// 遍歷當(dāng)前層數(shù)據(jù)
for stackData.Len() > 0 {
currentNode := stackData.Front()
stackData.Remove(currentNode)
current := currentNode.Value.(*TreeNode)
// 當(dāng)前數(shù)據(jù)保存
tmpRet = append(tmpRet, current.Val)
// 左,右節(jié)點(diǎn)依次入隊(duì)列處理
if current.Left != nil {
stackData1.PushBack(current.Left)
}
if current.Right != nil {
stackData1.PushBack(current.Right)
}
}
res = append(res, tmpRet)
// 交換新舊隊(duì)列位置
stackData = stackData1
// 層數(shù)加1
index++
}
return res
}
// 層序遍歷的遞歸
func layer(root *TreeNode) [][]int {
res := make([][]int, 0)
var layerDeliver func(root *TreeNode, layer int)
layerDeliver = func(root *TreeNode, layer int) {
if root == nil {
return
}
if len(res) == layer {
res = append(res, make([]int, 0))
}
res[layer] = append(res[layer], root.Val)
layer++
layerDeliver(root.Left, layer)
layerDeliver(root.Right, layer)
}
layerDeliver(root, 0)
return res
}
/*
后序遍歷:
先從左到右 ,先葉子后節(jié)點(diǎn)的方式遍歷訪問左右子樹值纱,最后訪問根節(jié)點(diǎn)
*/
func after(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
left := after(root.Left)
right := after(root.Right)
return append(append(left, right...), root.Val)
}
func afterLoop(root *TreeNode) []int {
var res []int
var prev *TreeNode
// 獲取棧處理
stack := list.New()
// 棧不為空或者根節(jié)點(diǎn)部位空的時(shí)候處理
for root != nil || stack.Len() > 0 {
// 一路往左走到底
for root != nil {
stack.PushBack(root)
root = root.Left
}
// 取出一個(gè)數(shù)據(jù)處理
tempNode := stack.Back()
stack.Remove(tempNode)
root = tempNode.Value.(*TreeNode)
// 右節(jié)點(diǎn)沒有處理過或者已經(jīng)處理過右節(jié)點(diǎn)鳞贷,則處理當(dāng)前節(jié)點(diǎn)
if root.Right == nil || root.Right == prev {
res = append(res, root.Val)
prev = root // 記錄下當(dāng)前處理節(jié)點(diǎn)
root = nil // 標(biāo)記該節(jié)點(diǎn)已經(jīng)處理完畢
} else {
// 右節(jié)點(diǎn)未處理過則需要入棧繼續(xù)處理
stack.PushBack(root)
root = root.Right
}
}
return res
}
/*
前序遍歷的定義:
先訪問根節(jié)點(diǎn),然后前序遍歷左子樹虐唠,再前序遍歷右子樹
遞歸方式
*/
func before(root *TreeNode) []int {
res := make([]int, 0)
var left, right []int
if root == nil {
return res
}
res = append(res, root.Val)
left = before(root.Left)
right = before(root.Right)
return append(append([]int{root.Val}, left...), right...)
}
func beforeLoop(root *TreeNode) []int {
res := make([]int, 0)
stackData := list.New()
for stackData.Len() > 0 || root != nil {
if root != nil {
res = append(res, root.Val)
stackData.PushBack(root)
root = root.Left
} else {
// 左子樹遍歷完畢再遍歷 右子樹
node := stackData.Back()
stackData.Remove(node)
nodeData := node.Value.(*TreeNode)
root = nodeData.Right
}
}
return res
}
/*
中序遍歷的定義:
先遍歷根節(jié)點(diǎn)的左子樹搀愧,然后訪問根節(jié)點(diǎn)的,最后遍歷右子樹
中序遍歷迭代
*/
func middleLoop(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
stackData := list.New()
// 需要一個(gè)棧來處理
for stackData.Len() > 0 || root != nil {
if root != nil {
stackData.PushBack(root)
root = root.Left
} else {
tmp := stackData.Back()
stackData.Remove(tmp)
tmpNode := tmp.Value.(*TreeNode)
res = append(res, tmpNode.Val)
root = tmpNode.Right
}
}
return res
}
/**
* 中序遍歷 - 遞歸
*/
func middle(root *TreeNode) []int {
var left, right []int
if root == nil {
return make([]int, 0)
}
// 處理左邊的數(shù)據(jù)
left = middle(root.Left)
right = middle(root.Right)
res := append(append(left, root.Val), right...)
return res
}