105. Construct Binary Tree from Preorder and Inorder Traversal
Medium
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 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]
Constraints:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorderandinorderconsist of unique values.- Each value of
inorderalso appears inpreorder. preorderis guaranteed to be the preorder traversal of the tree.inorderis guaranteed to be the inorder traversal of the tree.
preorder 陣列中，中間節點會在最前面。
inorder 陣列中，中間節點左邊為左子樹，右邊為右子樹。
所以我們可以每次將 preorder 陣列第一個元素抓出來，在 inorder 搜尋該元素，將元素左半進行遞迴呼叫視為元素的左子樹，右半則是右子樹。
/**
* 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 {
return nil
}
node := &TreeNode{ Val:preorder[0] }
if len(preorder) == 1 {
return node
}
i := findIndex(inorder, preorder[0])
node.Left = buildTree(preorder[1:i+1], inorder[0: i])
node.Right = buildTree(preorder[i+1:], inorder[i+1:])
return node
}
func findIndex(arr []int, target int) int {
for i, n := range arr {
if n == target {
return i
}
}
return -1
}