Construct Binary Tree from Preorder and Inorder Traversal
Two arrays describe the same binary tree: preorder lists its values in preorder (node, left subtree, right subtree) and inorder lists them in inorder (left subtree, node, right subtree). All values in the tree are distinct.
Rebuild the tree and return its root. The tests show the returned tree as a level-order list with null for missing children.
Constraints
1 <= preorder.length <= 3000inorder.length === preorder.length-3000 <= preorder[i], inorder[i] <= 3000- Every value is distinct, and both arrays are valid traversals of the same tree.
Examples
Example 1
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
The first preorder value, 3, is the root. In the inorder list, 9 is left of 3 (the left subtree) and 15, 20, 7 are right of it.
Example 2
Input: preorder = [-1], inorder = [-1] Output: [-1]
A single node is its own preorder and inorder.
Example 3
Input: preorder = [1,2,4,5,3,6,7], inorder = [4,2,5,1,6,3,7] Output: [1,2,3,4,5,6,7]
A perfect tree with three levels.
JavaScript you'll use: Recursion, the call stack and memoization Linked list and tree nodes
/**
* Tree nodes are provided (you don't need to define them):
* class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
function buildTree(preorder, inorder) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.