106. 从中序与后序遍历序列构造二叉树

1. 题目描述

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

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

例如，给出

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

2. 解题思路

这个题目的思路也是使用递归：

• 我们可以知道，后序遍历数组的最后一个值是二叉树的根节点，也就是上面的7
• 根据根节点的值，在中序遍历的数组中找到该值的索引，我们就可以知道，3左边的是左子树的中序遍历的数组，3后面的是右子树的中序遍历的数组
• 根据根节点的值，在后续遍历数组中找到的该值得索引，我们就可以知道，0到该索引的的值都是左子树的后序遍历的数组，后面的数值就是右子树的后序遍历的数组（需要排除根节点）

• 根据上面得到的左右子树的中序遍历和后续遍历的结果进行递归操作

  3. 代码实现

  /**
  * Definition for a binary tree node.
  * function TreeNode(val) {
  *     this.val = val;
  *     this.left = this.right = null;
  * }
  */
  /**
  * @param {number[]} inorder
  * @param {number[]} postorder
  * @return {TreeNode}
  */
  var buildTree = function(inorder, postorder) {
    if(!inorder.length) return null
    let len = postorder.length
    let tmp = postorder[len-1]
    let mid = inorder.indexOf(tmp)
    let root = new TreeNode(tmp)
    root.left = buildTree(inorder.slice(0,mid), postorder.slice(0,mid))
    root.right = buildTree(inorder.slice(mid + 1), postorder.slice(mid,len-1))
    return root
  };

  4. 提交结果