Build a tree from preorder and inorder
Mediumtreedivide and conquerhash maprecursion
preorder visits nodes as (node, left, right) and inorder as (left, node, right), for the same tree. Values are distinct. Rebuild the tree and return its root.
Examples write a tree level by level, with null for a missing child: [3,9,20,null,null,15,7].
Example 1
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
Example 2
Input: preorder = [-1], inorder = [-1] Output: [-1]
Constraints
- 1 ≤ preorder.length ≤ 3000
- inorder.length == preorder.length
- Values are distinct
Submit checks your solution against 8 tests, including hidden ones.
// Provided by the judge: keep these definitions
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val
this.left = left
this.right = right
}
}
/**
* @param {int[]} preorder
* @param {int[]} inorder
* @return {TreeNode|null}
*/
function buildTree(preorder, inorder) {
}