Prompt: Given two lists of integers, one is the preorder traversal of a binary tree and the other is the inorder traversal of the same tree. The goal is to reconstruct the binary tree and return the root node.
Example:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Solution: In preorder traversal, all subnodes are to the right of the current node. In inorder traversal, all left sub nodes are to the left of the current node and all right sub nodes are to the right of the current node.
Knowing this, we can use recursion to rebuild the binary tree. We can access the very first node of the preorder list and have that as the current node. For each recursion, we want to make that first node and cut it off in the preorder list in order to prevent a loop.
Since we have the current node, we need the left sub nodes and right sub nodes. We can find the current node value in the inorder list and recurse to the left subtree and right subtree as the left node and right node of the current node. Since all nodes are created from the first element of the preorder list, the inorder list would be empty when you hit a leaf node. For that case, we can return a None when we hit a leaf node.
The runtime for this solution is O(n) since we have to go through all nodes.