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