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

题目#

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

思路#

相信了解二叉树的前中后三种遍历顺序的大家都会手动地推导出树的结构。

具体到这道题，就是通过前序遍历确定每一次的根节点，再通过根节点的值划分左右子树。

代码#

// 递归过程
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(preorder) != len(inorder) {
        return nil
    }
    // 由前序遍历确定根节点
    root := &TreeNode{preorder[0], nil, nil}

    // 获取左右子树
    i := findIndex(inorder, preorder[0])
    // 分别重建左右子树
    root.Left = buildTree(preorder[1:1+i], inorder[:i])
    root.Right = buildTree(preorder[i+1:], inorder[i+1:])

    return root
}

// 在中序遍历中找到根节点位置，划分左右子树
func findIndex(arr []int, num int) int {
    index := 0
    // O(n) 操作，可以优化为二分查找
    for i, n := range arr {
        if num == n {
            index = i
            break
        }
    }

    return index
}