class TreeNode(object):
def __init__(self,x):
self.val = x
self.left = None
self.right = None
class Solution(object):
tree = None
pre = []
post = []
end = []
def preorder(self,root):
if not root:
return
self.pre.append(root.val)
self.preorder(root.left)
self.preorder(root.right)
def postorder(self,root):
if not root:
return
self.postorder(root.left)
self.postorder(root.right)
self.post.append(root.val)
def endnode(self,root):
if not root:
return []
queue1 = [root]
queue2 = []
while queue1:
cur = queue1.pop(0)
if not cur.left and not cur.right:
self.end.append(cur.val)
if cur.left:
queue2.append(cur.left)
if cur.right:
queue2.append(cur.right)
if queue1 == []:
queue1 = queue2
queue2 = []
def build(self, sub_levelorder, sub_inorder):
if sub_inorder == []:
return None
root_value = sub_levelorder[0]
root = TreeNode(root_value)
index = sub_inorder.index(root_value)
left_sub_inorder = sub_inorder[:index]
right_sub_inorder = sub_inorder[index + 1:]
left_sub_levelorder,right_sub_levelorder = [],[]
# 按照层次遍历，第一个出现的就是根节点，然后找到中序中根节点的位置，分成左右两个子树的中序。再根据这个中序的序列，找到左右子树层次遍历的序列
# 考试的时候这一步没做好，一直做不出来，看了@ningshixian的做法。
for each in sub_levelorder[1:]:
if each in left_sub_inorder:
left_sub_levelorder.append(each)
else:
right_sub_levelorder.append(each)
root.left = self.build(left_sub_levelorder, left_sub_inorder)
root.right = self.build(right_sub_levelorder, right_sub_inorder)
return root
def buildTree(self, levelorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if levelorder == [] or inorder == []:
return None
self.tree = self.build(levelorder, inorder)
