105. Construct Binary Tree from Preorder and Inorder Traversal

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

/**
 * 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) {
  return helper(preorder, inorder, 0, 0, inorder.length - 1);
};

var helper = function (preorder, inorder, preIndex, inStart, inEnd) {
  if (preIndex >= preorder.length || inStart > inEnd) return null;

  var index = 0;
  var root = new TreeNode(preorder[preIndex]);

  for (var i = inStart; i <= inEnd; i++) {
    if (inorder[i] === root.val) {
      index = i;
      break;
    }
  }

  if (index > inStart) root.left = helper(preorder, inorder, preIndex + 1, inStart, index - 1);
  if (index < inEnd) root.right = helper(preorder, inorder, preIndex + index - inStart + 1, index + 1, inEnd);

  return root;
};

Explain:

1. preorder[0] 是 root
2. 在 inorder 里找到 root，左边是 root.left，右边是 root.right。
3. 递归

Complexity:

• Time complexity :
• Space complexity :