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

1. 题目描述

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

2. 思路

1. 思路一
   • 前序遍历第一个元素是 root
   • 根据这个 root 在中序遍历中的位置把中序分两半，左半对应左子树，右半对应右子树
   • 注意这里不是二叉搜索树，因此中序遍历不是有序的

3. 实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 { return nil }
    rootVal := preorder[0]
    idx := find(inorder, rootVal)
    root := &TreeNode{Val: rootVal}
    root.Left = buildTree(preorder[1:idx+1], inorder[:idx])
    root.Right = buildTree(preorder[idx+1:], inorder[idx+1:])
    return root
}

func find(nums []int, target int) int {
    for i, num := range nums {
        if num == target { return i }
    }
    return -1
}

4. 参考

• 详细通俗的思路分析，多解法 - 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）