105.从前序与中序遍历序列构造二叉树.js

/*
 * @lc app=leetcode.cn id=105 lang=javascript
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * 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 === 0) return null // inorder不能再划分了
  	let root = new TreeNode(preorder[0]) // 构建root
  	let mid = inorder.indexOf(preorder[0]) // 找到root在inorder的位置
  	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
};
// @lc code=end