Leetcode: Reconstruct binary tree
Given two lists of a preorder
and inorder
, create a tree and return the root
node.
preorder: [3,9,20,15,7]
inorder: [9,3,15,20,7]
Resulting tree:
3
/ \
9 20
/ \
15 7
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 inorder
list.
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 root
node.
from typing import List, Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self) -> str:
"""Convenience function for easy debugging"""
return str(self.val)
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if len(preorder) == 0:
return None
def inner(root, preorder, left, right):
if len(preorder) == 0:
return
# Determine if the element is left or right
curr = preorder[0]
idx = -1
for i in range(len(left)):
if left[i] == curr:
idx = i
break
# Next element is in the left part
if idx > -1:
root.left = TreeNode(curr)
inner(root.left, preorder[1:], left[:idx], left[idx+1:])
preorder = preorder[len(left):]
idx = -1
for i in range(len(right)):
if right[i] == preorder[0]:
idx = i
break
if idx > -1:
root.right = TreeNode(preorder[0])
inner(root.right, preorder[1:], right[:idx], right[idx+1:])
root = TreeNode(preorder[0])
idx = -1
for i in range(len(inorder)):
if inorder[i] == preorder[0]:
idx = i
inner(root, preorder[1:], inorder[:idx], inorder[idx+1:])
return root
if __name__ == '__main__':
s = Solution().buildTree
t1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
# print(s([3,9,20,15,7,81], [9,3,15,20,81,7]), t1)
print(s([3,1,2,4], [1,2,3,4]))
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.