Binary Trees Building and serializing
379. Construct Binary Tree from Preorder and Inorder Traversal
You are given two integer arrays, preorder and inorder. They are the preorder and the inorder traversal of
the same binary tree. Build that tree and return its root.
A preorder traversal lists a node, then its left subtree in preorder, then its right subtree in preorder. An inorder traversal lists the left subtree in inorder, then the node, then the right subtree in inorder. All the values in the tree are distinct.
The output shows the tree you return level by level, from left to right, with null where a child is missing.
So [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The missing
children after the last node are left out.
Example 1
Input: preorder = [5, -2, 7, 0, 9, 4]
inorder = [7, -2, 0, 5, 4, 9]
[5,-2,9,7,0,4]Explanation: The tree has the root 5. Its left child -2 has the children 7 and 0, and its right child 9 has a left child 4. Listing node, left, right from the root gives 5, -2, 7, 0, 9, 4, and listing left, node, right gives 7, -2, 0, 5, 4, 9.
Example 2
Input: preorder = [-1000000000], inorder = [-1000000000]
[-1000000000]Explanation: One value, so the tree is a single node.
Example 3
Input: preorder = [4, 1, 3], inorder = [1, 3, 4]
[4,1,null,null,3]Explanation: The root 4 has a left child 1, and 1 has a right child 3. The root has no right child, and 1 has no left
child, so the output shows null in both places.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ preorder.length ≤ 105inorder.length == preorder.length-109 ≤ preorder[i], inorder[i] ≤ 109- All the values are distinct.
preorderandinorderare the preorder and inorder traversals of one binary tree.- That tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.