您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【golang必备算法】二叉树遍历(迭代)

二叉树遍历(迭代)

144. 二叉树的前序遍历

func preorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil{
        return res
    }
    strack := []*TreeNode{}
    strack = append(strack,root)

    for len(strack)>0{
        temp := strack[len(strack)-1]
        res = append(res,temp.Val)
        strack = strack[:len(strack)-1]
        //因为是栈,先放右节点
        if temp.Right != nil{
            strack = append(strack,temp.Right)
        }
        if temp.Left != nil{
            strack = append(strack,temp.Left)
        }

    }
    return res

}

94. 二叉树的中序遍历

func inorderTraversal(root *TreeNode) []int {
    strack := []*TreeNode{}
    cur := root
    res := []int{}

    for cur!=nil || len(strack)>0{
        if cur != nil{
            strack = append(strack,cur)
            cur = cur.Left
        }else{
            temp := strack[len(strack)-1]
            strack = strack[:len(strack)-1]
            res = append(res,temp.Val)
            cur = temp.Right
        }
    }
    return res
}

145. 二叉树的后序遍历

后序遍历是 左右中 ,而前序遍历是 中左右 ,所以把前序遍历顺序改一下再反转就是后序遍历

func postorderTraversal(root *TreeNode) []int {
    res := []int{}
    if root == nil{
        return res
    }
    strack := []*TreeNode{}
    strack = append(strack,root)

    for len(strack)>0{
        temp := strack[len(strack)-1]
        res = append(res,temp.Val)
        strack = strack[:len(strack)-1]

        //这里先放左节点,再放右节点,得到的就是 中右左,再反转就是后序遍历
        if temp.Left != nil{
            strack = append(strack,temp.Left)
        }
        if temp.Right != nil{
            strack = append(strack,temp.Right)
        }
    }
    return fanzhuan(res)
}

func fanzhuan(res []int)[]int{
    for i:=0;i<len(res)/2;i++{
        res[i],res[len(res)-1-i] = res[len(res)-1-i],res[i]
    }
    return res
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进