889. 根据前序和后序遍历构造二叉树

题目

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

题解

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} pre
 * @param {number[]} post
 * @return {TreeNode}
 */
var constructFromPrePost = function(pre, post) {
  let n = pre.length;
  if (!n) return null;
  let root = new TreeNode(pre[0]);
  if (n == 1) return root;

  // 左子树长度
  let l = post.indexOf(pre[1]) + 1;

  root.left = constructFromPrePost(pre.slice(1, l + 1), post.slice(0, l));
  root.right = constructFromPrePost(pre.slice(l + 1), post.slice(l));
  return root;
};