【LeetCode 105】从前序与中序遍历序列构造二叉树

叁歲伎倆 2022-11-30 01:58 106阅读 0赞

相似题目：

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

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

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

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

例如，给出

前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

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

对于这道题，我们先看下前序遍历和中序遍历的规律：

前序遍历的顺序是根节点、左子节点、右子节点，所以数组第一个值就是二叉树的根节点，然后我们看中序遍历，中序遍历的顺序是左子节点、根节点、右子节点，所以我们可以根据上面获得根据点判断，哪些是左子节点，哪些是右子节点，依次这样判断即可。

就拿上面的例子来说，我们从前序遍历数组中看出3是二叉树的根节点，然后在中序遍历数组中，我们可以知道3之前的都是左子节点，3之后的都是右子节点，3就是它们的中间值。我们在分别截出左右子节点的前序和中序遍历的数组，进行递归操作，就可以得到相应的二叉树。

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

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

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

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

[LeetCode 106]: https://blog.csdn.net/qq_42033567/article/details/108176759
[LeetCode 889]: https://blog.csdn.net/qq_42033567/article/details/108176496
[20200822223208997.png]: /images/20221124/8b79acfdb21a45e1a55d968ff1d4626e.png?