一、简介

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树

    3
   / \
  9  20
    /  \
   15   7

二、解法

分析：

中序遍历：先左子树，后根节点，再右子树；

后序遍历：先左子树，后右子树，再根节点。

所以，

可以基于后续遍历，确定根节点

基于根节点和中序遍历，可以确定左右子树 

于是，我们就可以得到下面两课树

重复上面分析，就可以得到该树

    3
   / \
  9  20
    /  \
   15   7

代码实现如下：

/**
 * 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) == 0 {
        return nil
    }
    
    // 取出根节点
    topVal := postorder[len(postorder) -1]
    
    var head = new(TreeNode)
    head.Val = topVal
    
    if len(inorder) == 1 {
        return head
    }
  
     // 取出中序遍历 左右树节点
    var topIndex int
    for inorder[topIndex] != topVal {
        topIndex ++
    } 
    var (
        inorderLeft []int
        inorderRight []int
    )
    inorderLeft = inorder[:topIndex]
    if topIndex < len(inorder) -1 {
        inorderRight = inorder[topIndex+1:]
    }
  
    if len(inorderLeft) > 0 {    
         postorderLeft := postorder[:len(inorderLeft)] // 后续遍历左树
         head.Left = buildTree(inorderLeft, postorderLeft)
    }
   
    if len(inorderRight) >0 {
         postorderRight := postorder[len(inorderLeft):len(postorder)-1] // 后续遍历右树
         head.Right = buildTree(inorderRight, postorderRight)
    }
    
    return head
}