Contents

# 105. Construct Binary Tree from Preorder and Inorder Traversal

## 題目 :

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

### Example :

Note

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1] Output: [-1]

#### 解題思路 :

• 這題的概念可以直接參考 leetcode106題解，一樣是重構binary tree，只是這題使用到的資源是preorder & inorder
• 這題只是將106題postorder數組該成preorder數組，從原本取得最後一個數作為root改成取第一個數作為root
• 然後recursive code裡，切分的slice range改變，若理解了106題，那這題就可以輕鬆完成!

### Recursive解法

• time complexity: O(n^2) , space complexity: O(n)

Runtime: 4 ms, faster than 91.79% of Go online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 `````` ``````/** * 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 } mid := preorder[0] midIndex := findIndex(inorder, mid) node := &TreeNode { Val: mid, Left: buildTree(preorder[1:midIndex+1], inorder[:midIndex]), Right: buildTree(preorder[midIndex+1:], inorder[midIndex+1:]), } return node } func findIndex( arr []int, tar int) int{ for i, v := range arr { if v == tar { return i } } return -1 } ``````