从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

最开始写出的代码，大概是

func buildTree(preorder []int, inorder []int) *TreeNode {
    rootOfLeftTree := buildTree(leftPreorder, leftInorder)
    rootOfRightTree := buildTree(rightPreorder, rightInorder)
    return &TreeNode{rootValue, rootOfLeftTree, rootOfRightTree}
}

这是后序遍历，分解问题法。但是确定leftPreorder的方法构造的不够好，应该注意到leftPreorder和leftInorder是一样长的。这里可以优化。

另外，其实根本不用传递数组，只需要传递preorder和inorder的起止的key，能减少空间。

最开始的代码

func getKeyOfElementInArray(element int, array []int) int {
    for key, value := range array {
        if value == element {
            return key
        }
    }
    return -1
}

func help(array1 []int, array2 []int) int {
    for key, value := range array1 {
        if getKeyOfElementInArray(value, array2) != -1 {
            return key
        }
    }
    return -1
}

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    if len(preorder) == 1 {
        return &TreeNode{preorder[0], nil, nil}
    }
    rootValue := preorder[0]
    keyOfRootInInorder := getKeyOfElementInArray(rootValue, inorder)

    leftInorder := inorder[:keyOfRootInInorder]
    rightInorder := inorder[keyOfRootInInorder+1:]

    maxPosOfLeftPreorder := help(preorder[1:], rightInorder)

    if maxPosOfLeftPreorder == -1 {
        maxPosOfLeftPreorder = len(preorder) - 1
    }

    leftPreorder := preorder[1 : maxPosOfLeftPreorder+1]
    rightPreorder := preorder[maxPosOfLeftPreorder+1:]

    // fmt.Println(leftPreorder, rightPreorder)
    // fmt.Println(leftInorder, rightInorder)
    rootOfLeftTree := buildTree(leftPreorder, leftInorder)
    rootOfRightTree := buildTree(rightPreorder, rightInorder)
    return &TreeNode{rootValue, rootOfLeftTree, rootOfRightTree}
}

优化之后的代码

var Preorder, Inorder []int

func help(preorderStartKey, preorderEndKey, inorderStartKey, inorderEndKey int) *TreeNode {
    if preorderEndKey-preorderStartKey == 0 {
        return nil
    }
    if preorderEndKey-preorderStartKey == 1 {
        return &TreeNode{Preorder[0], nil, nil}
    }
    rootValue := preorderStartKey
    keyOfRootInInorder := getKeyOfElementInArray(rootValue, Inorder[inorderStartKey:inorderEndKey+1])

    rightInorderStartKey := keyOfRootInInorder + 1
    rightInorderEndKey := inorderEndKey

    leftInorderStartKey := preorderStartKey + 1
    leftInorderEndKey := keyOfRootInInorder - 1

    leftPreorderStartKey := preorderStartKey + 1
    leftPreorderEndKey := preorderStartKey + (leftInorderEndKey - leftInorderStartKey)

    rightPreorderStartKey := leftPreorderEndKey + 1
    rightPreorderEndKey := preorderEndKey

    rootOfLeftTree := help(leftPreorderStartKey, leftPreorderEndKey, leftInorderStartKey, leftInorderEndKey)
    rootOfRightTree := help(rightPreorderStartKey, rightPreorderEndKey, rightInorderStartKey, rightInorderEndKey)
    return &TreeNode{rootValue, rootOfLeftTree, rootOfRightTree}
}

func buildTree(preorder []int, inorder []int) *TreeNode {
    Preorder, Inorder = preorder, inorder
    return help(0, len(preorder)-1, 0, len(inorder)-1)
}