二叉树深度遍历 通解dfs 👌

中前后的顺序：迭代

//中序
func inorderTraversal(root *TreeNode) []int{
    res := []int{}
    stack := []*TreeNode{}
    for root != nil || len(stack) >0 {
        for root != nil {               
            stack = append(stack,root)      //压栈
            root = root.Left                //前
        }
        root = stack[len(stack)-1]      
        stack = stack[:len(stack)-1]    
        res = append(res,root.Val)          //中
        root = root.Right                   //后
    }
    return res
}

//前序
func preorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    res := []int{}

    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)        //压栈
            res = append(res, root.Val)     //中
            root = root.Left                //前
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        root = root.Right                    //后
    }
    return res
}

后序看不懂，换颜色标记法吧！
//1，递归法，后序-左右中
func preorderTraversal(root *TreeNode) []int {
    res := []int{}      //暂存一个数组 来存二叉树的值
    preorder(root, &res) //递归函数，父节点，遍历值
    return res          //返回结果数组
}

func preorder(root *TreeNode, res *[]int) {
    if root == nil {        //终止条件，根节点为空
        return
    }

    preorder(root.Left,res)  //中序遍历，前中后子树，核心三句，左
    preorder(root.Right,res)    //用递归函数的方式，取右节点值，右
    *res = append(*res,root.Val) //换这行位置，插入左右的区间内，中

}

颜色标记法：通法

重头戏来了，接下来介绍一下统一写法。
我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。
如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种也可以叫做标记法。

//3,颜色标记法,通法=变化顺序即可，反序变颜色，人工维护一个栈，==迭代的思路，例子是右左中 前序

func inorderTraversal(root *TreeNode) []int {
    type node struct {      //1,定义颜色，0表示白色，为遍历，1表示灰色，遍历过
        Color int
        Node *TreeNode
        }

    stack := make([]node, 0)    //2,初始化栈，手动维护
    rootNode := node{0, root}    //初始化根节点
    stack = append(stack, rootNode) //3,把根节点依次放入栈中，第一次入栈
    res := make([]int,0)

    for len(stack) >0 {             //4,入栈的模拟，父节点依次入栈
        root := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if n.Node == nil {          //5,入栈模拟，结束条件，没有父节点时
            continue
        }

        if root.Color == 0 {           //6.入栈模拟,核心，对白色的，未标记的进行遍历，入栈右中左,反序出栈
            stack = append(stack, node{0, root.Node.Right})
            //stack = append(stack, node{1, root.Node}) //访问后，白色变灰色
            stack = append(stack, node{0, root.Node.Left})
            stack = append(stack, node{1, root.Node}) //变一下这行就行

        } else {
            res = append(res , root.Node.Val)  
            //7,颜色为灰色，因为中序中根节点会被访问2次，输出第二次访问结果
        }
    }
    return res
}

//颜色标记法，核心反着存储，比如后序--左右中，他是中右左—-进栈
func inorderTraversal(root *TreeNode) []int {
    if root==nil{
       return nil
    }

    stack:=list.New()        //遍历栈
    res:=[]int{}            //结果集
    stack.PushBack(root)    //弹出栈顶，父节点

    var node *TreeNode        //暂存的root根节点

    for stack.Len()>0{
        e := stack.Back()    //返回栈，啥意思？
        stack.Remove(e)        //移除栈顶元素

        if e.Value==nil{        // 如果为空，则表明是需要处理中间节点
            e=stack.Back()        //弹出元素（即中间节点）
            stack.Remove(e)        //删除中间节点
            node=e.Value.(*TreeNode)
            res=append(res,node.Val)    //将中间节点加入到结果集中
            continue                    //继续弹出栈中下一个节点
        }
        node = e.Value.(*TreeNode)
        //压栈顺序：右中左
        if node.Right!=nil{
            stack.PushBack(node.Right)    //后
        }

        stack.PushBack(node)            //中，中间节点压栈后再压入nil作为中间节点的标志符
        stack.PushBack(nil)                //其实就是这两行放的位置，在两个if上下区间

        if node.Left!=nil{
            stack.PushBack(node.Left)    //前，左中右，中序遍历
        }
    }
    return res
}