Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a list of unique integers preorder and another list of unique integers inorder, representing the pre-order and in-order traversals of a binary tree, reconstruct the tree and return the root.
Constraints
n ≤ 100,000 where n is the length of preorder and inorder
Example 1
Input
preorder = [4, 2, 1, 0, 3]
inorder = [2, 1, 0, 3, 4]
Algorithm to Construct Binary Tree From Pre/Inorder Traversals
Given preorder, we know the root is the first element. And then, we can look for the root in the inorder, and use the index to separate the left and right tree. The following Python code uses pop(0) which takes O(N) time, and thus the overall complexity is O(N^2).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def constructBinaryTree(self, preorder, inorder): if inorder: i = inorder.index(preorder.pop(0)) return Tree( inorder[i], left=self.solve(preorder, inorder[:i]), right=self.solve(preorder, inorder[i+1:]), ) |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructBinaryTree(self, preorder, inorder):
if inorder:
i = inorder.index(preorder.pop(0))
return Tree(
inorder[i],
left=self.solve(preorder, inorder[:i]),
right=self.solve(preorder, inorder[i+1:]),
)Another implementation with same idea:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def constructBinaryTree(self, preorder, inorder): if not inorder or not preorder: return None rootVal = preorder.pop(0) i = inorder.index(rootVal) root = Tree(rootVal) root.left = self.solve(preorder, inorder[:i]) root.right = self.solve(preorder, inorder[i+1:]) return root |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructBinaryTree(self, preorder, inorder):
if not inorder or not preorder:
return None
rootVal = preorder.pop(0)
i = inorder.index(rootVal)
root = Tree(rootVal)
root.left = self.solve(preorder, inorder[:i])
root.right = self.solve(preorder, inorder[i+1:])
return rootAn alternative Recursive implmentation to construct the binary tree from pre-order and in-order is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | # class Tree: # def __init__(self, val, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def constructBinaryTree(self, preorder, inorder): if (not preorder) or (not inorder): return None root = Tree(preorder[0]) p = inorder.index(preorder[0]) root.left = self.solve(preorder[1:p+1], inorder[:p]) root.right = self.solve(preorder[p+1:], inorder[p+1:]) return root |
# class Tree:
# def __init__(self, val, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructBinaryTree(self, preorder, inorder):
if (not preorder) or (not inorder):
return None
root = Tree(preorder[0])
p = inorder.index(preorder[0])
root.left = self.solve(preorder[1:p+1], inorder[:p])
root.right = self.solve(preorder[p+1:], inorder[p+1:])
return rootTime complexity is O(N^2) and space complexity is also O(N^2).
See also: How to Construct Binary Search Tree from Preorder Traversal in Python?
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Algorithm to Truncate Sentence
Next Post: ASCII String to Integer Conversion Algorithm
