golang实现(递归+迭代)二叉树的遍历前序中序和后序

二叉树的遍历

前序遍历：

递归方法：

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

迭代方法：

func preorder(root *TreeNode)[]int {
    stack := []*TreeNode{}
    vals := []int{}
    node := root
     for node != nil || len(stack) > 0 {
         // 栈不为空
        for node != nil {
            // 前序遍历 先写入根节点值  再迭代左节点 直到左叶子结点
            //然后遍历右叶子结点 中左右
            vals = append(vals, node.Val)
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1].Right
        stack = stack[:len(stack)-1]
    }
    return vals
}

中序遍历：

递归方法:

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

迭代方法：

func inorder(root *TreeNode)[]int{
    ret := []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]
        //将结点值写入 遍历右孩子 左中右 
        ret = append(ret , root.Val)
        root=root.Right
    }
    return ret   
}

后序遍历

递归方法：

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

迭代方法：

func postorderTraversal(root *TreeNode) (res []int) {
    stk := []*TreeNode{}
    var prev *TreeNode
    //左右中
    for root != nil || len(stk) > 0 {
        for root != nil {
            stk = append(stk, root)
            root = root.Left
            //遍历到左叶子结点
        }
        root = stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        // 需要先写入右孩子节点 判断右孩子是否为空 为空就填值 不为空就放回栈 遍历右孩子的子树
        if root.Right == nil || root.Right == prev {
            res = append(res, root.Val)
            prev = root
            root = nil
        } else {
            stk = append(stk, root)
            root = root.Right
        }
    }
    return
}