前序遍历
约 568 字大约 2 分钟
前序遍历
前序遍历(根,左,右)
- 访问当前节点
- 调用当前节点左节点进行遍历
- 调用当前节点的右节点进行遍历
常用方式
- 递归,方案比较简单,方式统一
- loop,孔乙己茴字有几种写法
代码
递归
递归方式处理比较简单,先处理当前节点,左,右
func preOrder(head *BinaryTree) {
if nil == head {
return
}
// 访问当前节点
fmt.Printf("key:%d,value:%d\n", head.key, head.value)
// 调用当前节点左节点进行遍历
preOrder(head.leftNode)
// 调用当前节点的右节点进行遍历
preOrder(head.rightNode)
}
loop
- 茴字的第一种写法
func preOrderWithLoopV1(head *BinaryTree) {
if nil == head {
return
}
stack := []*BinaryTree{head}
for len(stack) > 0 {
pop := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Printf("key:%d,value:%d\n", pop.key, pop.value)
if nil != pop.rightNode {
stack = append(stack, pop.rightNode)
}
if nil != pop.leftNode {
stack = append(stack, pop.leftNode)
}
}
}
- 茴字的第二种写法,这种比较废人
func preOrderWithLoopV2(head *BinaryTree) {
var stack []*BinaryTree
node := head
for node != nil || len(stack) > 0 {
for node != nil {
fmt.Printf("key:%d,value:%d\n", node.key, node.value)
stack = append(stack, node)
node = node.leftNode
}
node = stack[len(stack)-1]
node = node.rightNode
stack = stack[:len(stack)-1]
}
}
loop进阶版
不使用递归,也不使用辅助栈,Morris traversal for Preorder
方式进行前序遍历
// 前序遍历,不使用递归和栈辅助
func preOrderWithLoopMorris(root *BinaryTree) {
if nil == root {
return
}
var predecessor *BinaryTree
var current = root
for current != nil {
// 如果当前节点的左孩子为空,直接打印当前节点,并转向处理右节点
if current.leftNode == nil {
fmt.Printf("key:%d,value:%d\n", current.key, current.value)
current = current.rightNode
} else {
// 查找当前节点的前驱节点
predecessor = current.leftNode
for predecessor.rightNode != nil && predecessor.rightNode != current {
predecessor = predecessor.rightNode
}
// 第一次前驱节点的右节点肯为空,这里就是将前驱节点的后继指向当前节点,然后继续向下走
if predecessor.rightNode == nil {
predecessor.rightNode = current
current = current.leftNode
} else {
// 如果回溯到当前节点,并且找前驱的时候,发现出了环,这个时候处理当前节点,并且向右移动
fmt.Printf("key:%d,value:%d\n", current.key, current.value)
predecessor.rightNode = nil
current = current.rightNode
}
}
}
}
总结
- 一般情况下使用递归写法简单,写起来比较快
- 使用
loop
方式,会在特殊情况下会有奇效,比如求每层二叉树平均值 - 在要求空间为常数,并且不能使用递归的情况下使用
Morris
,基本属于hard
级别