binary-tree
divide-and-conquer
recursion
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.
You may assume all node values in the tree are unique (so any value can be located in inorder unambiguously).
Input / output
- Input:
preorder: int[],inorder: int[] - Output:
TreeNode(JSON test fixture is a LeetCode-style level-order array, e.g.[3,9,20,null,null,15,7], withnullfor a missing child)
Constraints
- 0 <= number of nodes <= 3,000
preorderandinorderconsist of unique values- Every value in
inorderalso appears inpreorder, and vice versa
Follow-up
How would this change if node values were not guaranteed unique? What extra information would you need?
Examples
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 (single node)
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Example 3 (empty tree)
Input: preorder = [], inorder = []
Output: []
🔒 6 hidden
Running will execute all 9 cases, including 6 hidden ones.