145.二叉树的后序遍历

s方法一：递归

//1，递归
func postorderTraversal(root *TreeNode) []int {
    res := []int{}      //暂存一个数组 来存二叉树的值
    inerder(root, &res) //递归函数，父节点，遍历值
    return res          //返回结果数组
}
func postorder(root *TreeNode, res *[]int) {
    if root == nil {        //终止条件，根节点为空
        return
    }
    postorder(root.Left,res)  //中序遍历，前中后子树，核心三句
    //*res = append(*res,root.Val)
    postorder(root.Right,res) //用递归函数的方式，取右节点值
    *res = append(*res,root.Val)
}

方法二：迭代

//迭代，看不懂呀
func postorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    res := []int{}
    var prev *TreeNode                        //新建一个树prev

    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]

        if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)     //中
            prev = root
            root = nil 
        } else {
            stack = append(stack, root)     //入栈，根节点
            root = root.Right               //后
        }
    }
    return res
}

方法三：颜色标记，迭代

//3,颜色标记法,通法=变化顺序即可，反序变颜色，人工维护一个栈，==迭代的思路
func postorderTraversal(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,入栈的模拟，父节点依次入栈
        n := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

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

        if n.Color == 0 {           //6.入栈模拟,核心，对白色的，未标记的进行遍历，入栈右中左,反序出栈
            stack = append(stack, node{0, n.Node.Right})
            stack = append(stack, node{0, n.Node.Left})

            stack = append(stack, node{1, n.Node}) //变一下这行就行
        } else {
            res = append(res , n.Node.Val)  
            //7,颜色为灰色，因为中序中根节点会被访问2次，输出第二次访问结果
        }

    }
    return res
}