Restore Binary Tree
Problem name: restoreBinaryTree
Problem description is here.
#
# Definition for binary tree:
# class Tree(object):
# def __init__(self, x):
# self.value = x
# self.left = None
# self.right = None
def restoreBinaryTree(inorder, preorder):
if len(preorder) == 0:
return None
root = Tree(preorder[0])
pivot = find_pivot(inorder, root)
if pivot is None:
return None
left_subtree = inorder[:pivot]
right_subtree = inorder[pivot+1:]
if len(left_subtree) == 1:
root.left = Tree(left_subtree[0])
elif len(left_subtree) == 0:
root.left = None
else:
root.left = restoreBinaryTree(left_subtree, preorder[1:len(left_subtree)+1])
if len(right_subtree) == 1:
root.right = Tree(right_subtree[0])
elif len(right_subtree) == 0:
root.right = None
else:
root.right = restoreBinaryTree(right_subtree, preorder[len(left_subtree)+1:])
return root
def find_pivot(pre, root):
for i in range(len(pre)):
if pre[i] == root.value:
return i
Time Complexity
O(N) # N is the length of BinaryTree
Solving Strategy
Root node is first node of preorder node because traversal order of preorder algorithm is ROOT - LEFT - RIGHT. When we find which node is root node, then we can distinguish left and right subtree from the root node. In this way, we can recursively build binary tree.
댓글남기기