二叉树的统一迭代法
要想统一写法就要:将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。
如何标记呢,就是要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。
前序遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
//前序:中 左 右 因此压栈顺序为:右 左 中
func preorderTraversal(root *TreeNode) []int {
var res []int
var stack []*TreeNode
if root!=nil{
stack=append(stack,root)
}
for len(stack)>0{
node:=stack[len(stack)-1]
if node!=nil{
stack=stack[:len(stack)-1]
if node.Right!=nil{
stack=append(stack,node.Right)//右
}
if node.Left!=nil{
stack=append(stack,node.Left) //左
}
stack=append(stack,node) //中
stack=append(stack,nil) //标记
}else{
stack=stack[:len(stack)-1]
node =stack[len(stack)-1]
stack=stack[:len(stack)-1]
res=append(res,node.Val)
}
}
return res
}
中序遍历
////中序:左 中 右 因此压栈顺序为:右 中 左
func inorderTraversal(root *TreeNode) []int {
var res []int
var stack []*TreeNode
if root!=nil{
stack=append(stack,root)
}
for len(stack)>0{
node:=stack[len(stack)-1]
if node!=nil{
stack=stack[:len(stack)-1]
if node.Right!=nil{
stack=append(stack,node.Right)//右
}
stack=append(stack,node) //中
stack=append(stack,nil) //标记
if node.Left!=nil{
stack=append(stack,node.Left) //左
}
}else{
stack=stack[:len(stack)-1]
node =stack[len(stack)-1]
stack=stack[:len(stack)-1]
res=append(res,node.Val)
}
}
return res
}
后序遍历
//后边序:左 右 中 因此压栈顺序为: 中 右 左
func postorderTraversal(root *TreeNode) []int {
var res []int
var stack []*TreeNode
if root!=nil{
stack=append(stack,root)
}
for len(stack)>0{
node:=stack[len(stack)-1]
if node!=nil{
stack=stack[:len(stack)-1]
stack=append(stack,node) //中
stack=append(stack,nil) //标记
if node.Right!=nil{
stack=append(stack,node.Right)//右
}
if node.Left!=nil{
stack=append(stack,node.Left) //左
}
}else{
stack=stack[:len(stack)-1]
node =stack[len(stack)-1]
stack=stack[:len(stack)-1]
res=append(res,node.Val)
}
}
return res
}
标签:node,nil,res,len,二叉树,迭代法,stack,append,统一
From: https://www.cnblogs.com/suehoo/p/17030071.html