Easy
根据二叉树的中根次序和后跟次序重建二叉树。假设没有重复。
Solution：
首先需要知道什么事二叉树的中根次序和后跟次序。下面三张图片对前中后跟次序做了清晰的解释[1]。
前跟次序
中跟次序
后跟次序
对序列有了认识，就可以从中根次序和后根次序的特点来思考问题的解决办法。可以看到后跟次序的最后一个数总是二叉树的根节点。一旦确立的树的根节点，则我们可以将该树分成左右两棵树，从而又称了递归问题。
注意，在做递归的时候，下面的方法有个小技巧：先对右支树做递归，是利用了pop()命令不断缩短postorder序列的特点，当右支树被遍历完成，postorder剩下的正好是左支数的postorder。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if not inorder or not postorder:
return None
root = TreeNode(postorder.pop())
root_index = inorder.index(root.val)
root.right = self.buildTree(inorder[root_index+1:],postorder)
root.left = self.buildTree(inorder[:root_index], postorder)
return root
-
Wikipedia_Tree traversal: https://en.wikipedia.org/wiki/Tree_traversal ↩
