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

描述

根据一棵树的中序遍历与后序遍历构造二叉树。
注意:你可以假设树中没有重复的元素。

示例 1：

题解

方法一：递归

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