[leetcode - Bliend-75 ] 105. Construct Binary Tree from Preo

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

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)