func preorderTraversal(root *TreeNode) []int {
res := []int{}
if root == nil{
return res
}
strack := []*TreeNode{}
strack = append(strack,root)
for len(strack)>0{
temp := strack[len(strack)-1]
res = append(res,temp.Val)
strack = strack[:len(strack)-1]
//因为是栈，先放右节点
if temp.Right != nil{
strack = append(strack,temp.Right)
}
if temp.Left != nil{
strack = append(strack,temp.Left)
}
}
return res
}
func inorderTraversal(root *TreeNode) []int {
strack := []*TreeNode{}
cur := root
res := []int{}
for cur!=nil || len(strack)>0{
if cur != nil{
strack = append(strack,cur)
cur = cur.Left
}else{
temp := strack[len(strack)-1]
strack = strack[:len(strack)-1]
res = append(res,temp.Val)
cur = temp.Right
}
}
return res
}
后序遍历是 左右中 ，而前序遍历是 中左右 ，所以把前序遍历顺序改一下再反转就是后序遍历
func postorderTraversal(root *TreeNode) []int {
res := []int{}
if root == nil{
return res
}
strack := []*TreeNode{}
strack = append(strack,root)
for len(strack)>0{
temp := strack[len(strack)-1]
res = append(res,temp.Val)
strack = strack[:len(strack)-1]
//这里先放左节点，再放右节点，得到的就是 中右左，再反转就是后序遍历
if temp.Left != nil{
strack = append(strack,temp.Left)
}
if temp.Right != nil{
strack = append(strack,temp.Right)
}
}
return fanzhuan(res)
}
func fanzhuan(res []int)[]int{
for i:=0;i<len(res)/2;i++{
res[i],res[len(res)-1-i] = res[len(res)-1-i],res[i]
}
return res
}