Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

利用 preorder 和 inorder 構建一個 Binary tree

Example

• Input
  • preorder = [3,9,20,15,7]
  • inorder = [9,3,15,20,7]
• Output: [3,9,20,null,null,15,7]

Step

Preorder 的特性 Preorder 的第一個 itme 是整顆 tree 的 root node，而利用 preorder[0] 的值尋找該 item 是在 Inorder 的哪一個 order，該 item 在 inorder 中他的左邊代表 tree 的 left sub tree 而右邊則是 right sub tree

接著 preorder 往下一個 item 移動並找到該 item 存在於 inorder 的哪一個地方，在 inorder 中該 item 的左邊沒有東西了，所以判定 left sub tree 到該 item 後便結束

preorder 接著往下並找到該 item 存在於 inorder 的那一個地方，而該 item 就是這顆 sub tree 的 root node，藉由該 item 找到該 root 的 left sub tree 和 right sub tree。

Coding

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
  if (!preorder.length || !inorder.length) return null;

  let root = new TreeNode(preorder[0]);
  // find where is root index in order array
  let midIdx = inorder.findIndex(o => o === preorder[0]);
    
  root.left = buildTree(preorder.slice(1, midIdx + 1), inorder.slice(0, midIdx));
  root.right = buildTree(preorder.slice(midIdx + 1), inorder.slice(midIdx + 1));

  return root;
};

Time complexity: O(n)