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 7null 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.