题目一

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
}