给定一个二叉树的中序与后序遍历结果,请你根据两个序列构造符合这两个序列的二叉树。
数据范围:二叉树的节点数满足
,节点上的值满足
,保证节点的值各不相同
例如输入[2,1,4,3,5],[2,4,5,3,1]时,
根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5},如下图所示:
[1],[1]
{1}
[2,1,4,3,5],[2,4,5,3,1]
{1,2,3,#,#,4,5}
package main //import "fmt" import . "nc_tools" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param inorder int整型一维数组 中序遍历序列 * @param postorder int整型一维数组 后序遍历序列 * @return TreeNode类 */ func buildTree( inorder []int , postorder []int ) *TreeNode { // write code here if len(postorder) == 0{ return nil } newNode := new(TreeNode) newNode.Val = postorder[len(postorder) - 1] for i := 0; i < len(inorder); i++{ if newNode.Val == inorder[i]{ newNode.Left = buildTree(inorder[:i], postorder[:i]) newNode.Right = buildTree(inorder[i+1:], postorder[i:len(postorder)-1]) return newNode } } return newNode }