# Construct Binary Tree from Inorder and Preorder Traversal

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*.

```
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
let hash = {};
inorder.forEach((e, i)=>{hash[e] = i});
let recur = function(start, end) {
if (start > end) return null;
let root = new TreeNode(preorder.shift());
root.left = recur(start, hash[root.val] - 1);
root.right = recur(hash[root.val] + 1, end);
return root;
}
return recur(0, inorder.length - 1);
};
```

## Related Problems

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one **sorted** list. The list should be made by splicing together the nodes of the first two lists.

Return *the head of the merged linked list*.

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

The LCA is defined as: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we **allow a node to be a descendant of itself**).”

You are given a **0-indexed** array of **unique** strings words.

A **palindrome pair** is a pair of integers (i, j) such that:

0 <= i, j < words.length,

i != j, and

words[i] + words[j] (the concatenation of the two strings) is a palindrome.

Return *an array of all the ***palindrome pairs*** of *words.

You must write an algorithm with O(sum of words[i].length) runtime complexity.