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