题解 | #实现二叉树先序，中序和后序遍历#

package main
import . "nc_tools"

func threeOrders( root *TreeNode ) [][]int {
    ret := make([][]int, 0)
    ret = append(ret, preorderTree(root), inorderTree(root), postorderTree(root))

    return ret
}


//递归前序
func preorderTree(root *TreeNode) []int {
    res := []int{}
    preorder(root, &res)
    return res
}

func preorder(root *TreeNode, res *[]int) {
    if root == nil {
        return
    }

    *res = append(*res, root.Val)
    preorder(root.Left, res)
    preorder(root.Right, res)
}


//递归后序
func postorderTree(root *TreeNode) []int {
    res := []int{}
    postorder(root, &res)
    return res
}

func postorder(root *TreeNode, res *[]int) {
    if root == nil {
        return 
    }

    postorder(root.Left, res)
    postorder(root.Right, res)
    *res = append(*res, root.Val)
}


//迭代中序
func inorderTree(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 inorderTree(root *TreeNode) []int {
    res := []int{}
    stack := []*TreeNode{}

    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
}
*/