【LeetCode 105】從前序與中序周遊序列構造二叉樹

相似題目：

• ​​【LeetCode 106】從中序與後序周遊序列構造二叉樹​​
• ​​【LeetCode 889】根據前序和後序周遊構造二叉樹​​

題目描述

根據一棵樹的前序周遊與中序周遊構造二叉樹。

注意:

你可以假設樹中沒有重複的元素。

例如，給出

前序周遊 preorder = [3,9,20,15,7]
中序周遊 inorder = [9,3,15,20,7]      

傳回如下的二叉樹：

3
   / \
  9  20
    /  \
   15   7      

解題思路

對于這道題，我們先看下前序周遊和中序周遊的規律：

前序周遊的順序是根節點、左子節點、右子節點，是以數組第一個值就是二叉樹的根節點，然後我們看中序周遊，中序周遊的順序是左子節點、根節點、右子節點，是以我們可以根據上面獲得根據點判斷，哪些是左子節點，哪些是右子節點，依次這樣判斷即可。

代碼實作

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

送出結果