题目一

leetcode:105

代码与解析一

这里放上b站一位大佬的视频:https://www.bilibili.com/video/BV1z4411B7AM?spm_id_from=333.999.0.0
https://www.bilibili.com/video/BV1o7411j7xk?spm_id_from=333.999.0.0

func buildTree(preorder []int, inorder []int) *TreeNode {
    var helper func (preorder *[]int, pstart int, pend int, inorder *[]int, istart int, iend int)*TreeNode
    helper = func (preorder *[]int, pstart int, pend int, inorder *[]int, istart int, iend int)*TreeNode{
        if pstart>pend||istart>iend{
            return nil
        }
        root := &TreeNode{Val: (*preorder)[pstart]}
        key := search(inorder, root.Val)

        leftLength := key - istart
        preStRight := pstart + leftLength + 1
        // 下一次左面的长度
        preStLeft := pstart + 1
        root.Left = helper(preorder, preStLeft, leftLength+pstart, inorder, istart, key-1)
        root.Right = helper(preorder, preStRight, pend, inorder, key+1, iend)
        return root
    }
    return helper(&preorder, 0, len(preorder)-1, &inorder, 0, len(inorder)-1)
}
func search(array *[]int, res int)int{
    for i, v:=range *array{
        if v==res{
            return i
        }
    }
    return -1
}

题目二

中序后序遍历构造二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

代码与解析二


这里放上b站一位大佬视频:
https://www.bilibili.com/video/BV1Y4411z7vc?spm_id_from=333.999.0.0
https://www.bilibili.com/video/BV1o7411j7xk?spm_id_from=333.999.0.0

func buildTree(inorder []int, postorder []int) *TreeNode {
    var helper func(inorder *[]int, istart int, iend int, postorder *[]int, pstart int, pend int) *TreeNode
    helper = func(inorder *[]int, istart int, iend int, postorder *[]int, pstart int, pend int) *TreeNode {
        if istart > iend || pstart <0 {
            return nil
        }
        root := &TreeNode{Val: (*postorder)[pend]}
        key := search(*inorder, root.Val)

        postLeft := pstart + key - istart
        postRight := pstart + key - istart - 1

        root.Left = helper(inorder, istart, key-1, postorder, pstart, postRight)
        root.Right = helper(inorder, key+1, iend, postorder, postLeft, pend-1)
        return root
    }
    return helper(&inorder, 0, len(inorder)-1, &postorder, 0, len(postorder)-1)
}
func search(array []int, value int) int {
    for i, v := range array {
        if value == v {
            return i
        }
    }
    return -1
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:459543 人次
ICP备案号: 辽ICP备20003309号