前言
中间又断更新。
正文
问题来源
本问题来自leetcode上的105题。
问题描述
根据一棵树的前序遍历与中序遍历构造二叉树。
示例 1:
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
3
/ \
9 20
/ \
15 7
分析：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildSubTree(preorder []int, inorder []int, pre_start, in_start, in_end int) *TreeNode {
if in_end < in_start {
return nil
}
rv := preorder[pre_start]
i := in_start
for ; i <= in_end; i++ {
if inorder[i] == rv {
break
}
}
//fmt.Println(i)
root := &TreeNode{}
root.Val = rv
root.Left = buildSubTree(preorder, inorder, pre_start+1, in_start, i-1)
root.Right = buildSubTree(preorder, inorder, pre_start-in_start+i+1, i+1, in_end)
return root
}
func buildTree(preorder []int, inorder []int) *TreeNode {
return buildSubTree(preorder, inorder, 0, 0, len(inorder)-1)
}
总结：
勤思考。
结语
不管怎么样好好加油。
