aloalgoConstruct Binary Tree from Preorder and Inorder Traversal
Medium
You are given two integer arrays, preorder and inorder.
Your task is to construct and return the binary tree that would result from these traversals.
You may assume that:
- The
preordertraversal visits the root node first, then recursively traverses the left subtree, and finally the right subtree. - The
inordertraversal recursively visits the left subtree, then the root node, and finally the right subtree.
Return the root of the constructed binary tree.
Example 1
Inputs
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
Output
Explanation:
From preorder [3,9,20,15,7], 3 is the root. In inorder [9,3,15,20,7], 9 is left of 3, and [15,20,7] are right of 3. Recursively build the left and right subtrees.
Example 2
Inputs
preorder = [-1]
inorder = [-1]
Output
Explanation:
A single node tree where both traversals consist of just that node.
Example 3
Inputs
preorder = []
inorder = []
Output
None
Explanation:
An empty tree results in empty preorder and inorder traversals.
Inputs
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
Output