function TreeNode (val) {
this.left = this.right = null;
function buildTree (preorder, inorder) {
if (preorder.length === 0 || inorder.length === 0) {
return constructNewNode(preorder, inorder, 0, preorder.length, 0, inorder.length);
function findInorderIndex (list, target) {
list.forEach((item, i) => {
function constructNewNode (preorder, inorder, preStart, preLength, inStart, inLength) {
const root = preorder[preStart];
const inOrderIndex = findInorderIndex(inorder, root);
const rootNode = new TreeNode(root);
if (inOrderIndex - inStart >= 1) {
rootNode.left = constructNewNode(preorder, inorder, preStart + 1, preStart + (inOrderIndex - inStart), inStart, inOrderIndex - 1);
if (inLength - inOrderIndex >= 1) {
rootNode.right = constructNewNode(preorder, inorder, preStart + (inOrderIndex - inStart) + 1, preLength, inOrderIndex + 1, inLength);
return (root || root === 0) ? rootNode : null;