Leetcode: Reconstruct binary tree
Given two lists of a
inorder, create a tree and return the
The problem is not so obvious at first. If the preorder list would also contain
null values for the places where the tree does not contain nodes, we could simply iterate over this list and reconstruct the tree from there. But since the
null values are missing, we also need to take a look at the
We know about the
preorder list that the traversal is as follows:
NLR. This means that first the node is visited, then we go recursively to the left, and then recursively to the right. For
inorder it is
LNR: We go recursively to the left, then output the node, and finally go to the right.
Because of those properties, we know that the
root node is the first one in the
preorder list. Since there is only one
root node, we know that the next node will be in the next level. We don’t know, from looking at the
preorder list, if the next child node is to the left or right. To figure this out, we need to look at the
inorder list. If the node is to the left of our current element, know that it must be the immediate child to the left. We then determine the position of the node in the
inorder list and pass it recursively to the same method.
If it is to the right, we remove the left prefix from the
preorder list, add it as a right node, and pass in the left and right lists to the recursive function. Finally, we return the
Runtime: 722 ms, faster than 5.01% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal. Memory Usage: 89.2 MB, less than 5.37% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.