递归

前序遍历

func preorder(root *TreeNode)[]int{
    res := make([]int, 0)
    var order func(*TreeNode)
    order = func (node *TreeNode){
        if node ==nil{
            return
        }
        // 递归方法  先写入值 再递归左节点 再递归右节点
        res = append(res,node.Val)
        order(node.Left)
        order(node.Right)
    }
    order(root)
    return res
}

中序遍历

func inorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := []*TreeNode{}
    node := root
    for node != nil || len(stack) > 0{
        res = append(res, node.Val)
        stack = append(stack, node)
        node = node.Left
    }
}

后序遍历

func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    var postorder func(*TreeNode)
    postorder = func(node *TreeNode){
        if node == nil{
            return
        }
        postorder(node.Left)
        postorder(node.Right)
        res = append(res, node.Val)
    }  
    postorder(root)
    return res
}

迭代

前序遍历

func preorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := []*TreeNode{}
    if root == nil{
        return res
    }
    node := root
    stack = append(stack, node)
    for len(stack) > 0{
        tmp := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        res = append(res, tmp.Val)
        if tmp.Right != nil{
            stack = append(stack, tmp.Right)
        }
        if tmp.Left != nil{
            stack = append(stack, tmp.Left)
        }
    }
    return res
}

中序遍历

思路：每到一个节点 A，因为根的访问在中间，将 A 入栈。然后遍历左子树，接着访问 A，最后遍历右子树。

在访问完 A 后，A 就可以出栈了。因为 A 和其左子树都已经访问完成。

func inorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := []*TreeNode{}
    if root == nil{
        return res
    }
    node := root
    for node != nil || len(stack) > 0{
        for node != nil{
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        res = append(res, node.Val)
        node = node.Right
    }
    return res
}

后序遍历

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

func postorderTraversal(root *TreeNode) []int {
    res := make([]int, 0)
    stack := []*TreeNode{}
    if root == nil{
        return res
    }
    node := root
    stack = append(stack, node)
    for len(stack) > 0{
        tmp := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        res = append(res, tmp.Val)
        if tmp.Left != nil{
            stack = append(stack, tmp.Left) // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
        }
        if tmp.Right != nil{
            stack = append(stack, tmp.Right) // 空节点不入栈
        }
    }
    for i := 0; i < len(res) / 2; i++{
        res[i], res[len(res) - i - 1] = res[len(res) - i - 1], res[i]
    }
    return res
}

使用slice模拟栈

普通版的模拟写入和读取的栈

package main
import "fmt"
//栈的特点是先进后出
//使用一个切片的全局变量来模拟栈
var stack []int
//向栈中添加数据
func push(value int) {
    stack = append(stack, value)
}
//从栈中获取数据
func pop() (int, bool) {
    ok := false
    value := 0
    if len(stack) > 0 {
        value = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        ok = true
        return value, ok
    } else {
        return value, ok
    }
}
func main() {
    //向栈中添加数据
    for i := 0; i < 10; i++ {
        push(i)
        fmt.Println(stack)
    }
    //从栈中获取数据
    for {
        v, ok := pop()
        if ok {
            fmt.Println(v)
        } else {
            break
        }
    }
}

使用goroutine来异步读取栈中数据或往栈中写入数据

package main
import (
    "fmt"
)
//栈的特点是先进后出
//使用一个切片的全局变量来模拟栈
var stack1 []int
//此通道用于通知主协程已经完成操作了
//但是此操作有可能不会输出全部数据
//因为添加数据和获取数据是异步的
//当获取数据的速度快于写入数据
//便不会输出全部数据
var e chan int = make(chan int)
//向栈中添加数据
func push1(value int) {
    stack1 = append(stack1, value)
    fmt.Println(stack1)
}
//从栈中获取数据
func pop1() {
    for {
        if len(stack1) > 0 {
            value := stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
            fmt.Println(value)
        } else {
            e <- 0
        }
    }
}
func main() {
    for i := 0; i < 10; i++ {
        go push1(i)
    }
    go pop1()
    <-e
}

参考：

https://m.imooc.com/article/271255