【LeetCode 889】根据前序和后序遍历构造二叉树

怼烎@ 2022-11-30 04:02 124阅读 0赞

相似题目：

*  [【LeetCode 105】从前序与中序遍历序列构造二叉树][LeetCode 105]
 *  [【LeetCode 106】从中序与后序遍历序列构造二叉树][LeetCode 106]

#### 题目描述 ####

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

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

#### 解题思路 ####

对于这道题目，

*  首先看前序遍历，就可以知道1是二叉树的根节点，那么紧跟其后的应该就是左节点，也就是2。
 *  在后序遍历中找到2对应的位置，我们就可以知道2及之前的数都是该二叉树的左节点的后序遍历数组，之后的数都是二叉树的右节点的后序遍历数组（需要除去根节点）
 *  根据左子树的长度在先序遍历中找到左子树和右子树的前序遍历值。
 *  进行递归操作，得出最后的二叉树。  
    ![在这里插入图片描述][20200822225439721.png]

#### 代码实现 ####

/** * 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;
    };

#### 提交结果 ####

![在这里插入图片描述][20200822225523922.png]

[LeetCode 105]: https://blog.csdn.net/qq_42033567/article/details/108176121
[LeetCode 106]: https://blog.csdn.net/qq_42033567/article/details/108176759
[20200822225439721.png]: /images/20221124/ea2d58a93051437db7b6d570ec23d36a.png?
[20200822225523922.png]: /images/20221124/d0ea07e3580d4fa98880634e506c63f8.png?