106. Construct Binary Tree from

题目

给定一颗二叉树的中序遍历和后序遍历结果，构造并返回这个二叉树。

解析

这个题和上一个题目几乎一致，中序遍历不变，只是根节点的寻找从前序变为后序。

伪代码

node = post[n]
k = findnode(in, node)
node.left = f(in[:k], post[:k])
node.right = f(in[k+1:], post[k：n])
return node

代码

func buildTree(inorder []int, postorder []int) *TreeNode {
    l:=len(postorder)
    if l == 0 {
        return nil
    }
    node := &TreeNode{Val:postorder[l-1]}
    k:=0
    for inorder[k] != postorder[l-1] {
        k++
    }
    node.Left = buildTree(inorder[:k], postorder[:k])
    node.Right = buildTree(inorder[k+1:], postorder[k:l-1])
    return node
}