根据一棵树的前序遍历与中序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
代码语言：javascript复制前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
代码语言：javascript复制 3
/
9 20
/
15 7解题思路：
1，前序遍历的话第一个一定是根
2，中序遍历的话和根元素相等的元素左边一定在左子树，设根元素位置为i
3，前序遍历，前长度为i 1的元素一定在左子树
4，递归求解
代码语言：javascript复制/**
* 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) < 1 || len(inorder) < 1 {
return nil
}
if len(preorder) == 1 {
return &TreeNode{
Val: preorder[0],
}
}
if len(inorder) == 1 {
return &TreeNode{
Val: inorder[0],
}
}
i := 0
for ; i < len(inorder); i {
if preorder[0] == inorder[i] {
break
}
}
if i == len(inorder) {
return nil
}
h := &TreeNode{
Val: preorder[0],
}
if i == 0 {
h.Right = buildTree(preorder[1:], inorder[i 1:])
} else if i == len(inorder)-1 {
h.Left = buildTree(preorder[1:], inorder[:i])
} else {
h.Left = buildTree(preorder[1:i 1], inorder[:i])
h.Right = buildTree(preorder[i 1:], inorder[i 1:])
}
return h
}根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
代码语言：javascript复制中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]返回如下的二叉树：
代码语言：javascript复制 3
/
9 20
/
15 7解题思路：
1，后序遍历的话最后一个一定是根
2，中序遍历的话和根元素相等的元素左边一定在左子树，设根元素位置为i
3，后序遍历，前长度为i 1的元素一定在左子树
4，递归求解
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(inorder)<1 ||len(postorder)<1{
return nil
}
if len(inorder)==1{
return &TreeNode{Val:inorder[0]}
}
i:=0
for ;i<len(inorder);i {
if postorder[len(postorder)-1]==inorder[i]{
break
}
}
h:=&TreeNode{Val:postorder[len(postorder)-1]}
if i==len(postorder)-1{
h.Left=buildTree(inorder[:i],postorder[:i])
}else if i==0{
h.Right=buildTree(inorder[1:],postorder[:len(postorder)-1])
}else{
h.Left=buildTree(inorder[:i],postorder[:i])
h.Right=buildTree(inorder[i 1:],postorder[i:len(postorder)-1])
}
return h
}
