class BTNode:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
'''
@ construct tree by inorder & preorder
'''
def constructByInPre(inorder, instart, inend, preorder, prestart, preend):
if inend < instart or preend < prestart:
return None
if len(preorder) != len( inorder ) :
return None
# preorder visit: root, left, right
for i in range(instart, inend + 1):
if inorder[i] == preorder[prestart]: break
if i > inend:
print "wrong data"
return None
root = BTNode(inorder[i])
root.left = constructByInPre(inorder, instart, i - 1, preorder, prestart + 1, preend)
root.right = constructByInPre(inorder, i + 1, inend, preorder, prestart + 2, preend)
return root
'''
@ construct tree by inorder & postorder
'''
def constructByInPost(inorder, instart, inend, postorder, posstart, posend):
if inend < instart or posend < posstart:
return None
if len(postorder) != len(inorder):
return None
# posterorder visit: left, right, root
for i in range(instart, inend + 1):
if inorder[i] == postorder[posend]: break
if i > inend:
print "wrong data"
return None
root = BTNode(inorder[i])
leftlen = i - instart
root.left = constructByInPost(inorder, instart, i - 1, postorder, posstart, posstart + leftlen - 1)
root.right = constructByInPost(inorder, i + 1, inend, postorder, posstart + leftlen, posend - 1)
return root