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

1. 题目描述

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

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

示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

提示：

• 1 <= pre.length == post.length <= 30
• pre[] 和 post[] 都是 1, 2, …, pre.length 的排列
• 每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

• 通过次数6,510提交次数9,886

  2. 解题思路

  对于这道题目：

• 首先看前序遍历，就可以知道1是二叉树的根节点，那么紧跟其后的应该就是左节点，也就是2。

• 在后序遍历中找到2对应的位置，我们就可以知道2及之前的数都是该二叉树的左节点的后序遍历数组，之后的数都是二叉树的右节点的后序遍历数组（需要除去根节点）
• 根据左子树的长度在先序遍历中找到左子树和右子树的前序遍历值。

• 进行递归操作，得出最后的二叉树。
  

  3. 代码实现

  /**
  * 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) {
    if(!pre.length) return null
    let tmp = pre[0];
    let index = post.indexOf(pre[1]);
    let root = new TreeNode(tmp);
    root.left = constructFromPrePost(pre.slice(1,index+2),post.slice(0,index+1));
    root.right = constructFromPrePost(pre.slice(index+2),post.slice(index+1,post.length-1));
    return root;
  };

  4. 提交结果