0105. Construct Binary Tree From Preorder and Inorder Traversal

# 105. Construct Binary Tree from Preorder and Inorder Traversal#

## 题目 #

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:You may assume that duplicates do not exist in the tree.

For example, given

``````preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
``````

Return the following binary tree:

``````    3
/ \
9  20
/  \
15   7
``````

## 解题思路 #

• 给出 2 个数组，根据 preorder 和 inorder 数组构造一颗树。
• 利用递归思想，从 preorder 可以得到根节点，从 inorder 中得到左子树和右子树。只剩一个节点的时候即为根节点。不断的递归直到所有的树都生成完成。

## 代码 #

``````
package leetcode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
inPos := make(map[int]int)
for i := 0; i < len(inorder); i++ {
inPos[inorder[i]] = i
}
return buildPreIn2TreeDFS(preorder, 0, len(preorder)-1, 0, inPos)
}

func buildPreIn2TreeDFS(pre []int, preStart int, preEnd int, inStart int, inPos map[int]int) *TreeNode {
if preStart > preEnd {
return nil
}
root := &TreeNode{Val: pre[preStart]}
rootIdx := inPos[pre[preStart]]
leftLen := rootIdx - inStart
root.Left = buildPreIn2TreeDFS(pre, preStart+1, preStart+leftLen, inStart, inPos)
root.Right = buildPreIn2TreeDFS(pre, preStart+leftLen+1, preEnd, rootIdx+1, inPos)
return root
}

``````

Sep 6, 2020