原题
中序遍历和后序遍历树构造二叉树
给出树的中序遍历： [1,2,3] 和后序遍历： [1,3,2]
返回如下的树：
2
/ \
1 3
你可以假设树中不存在相同数值的节点
解题思路
- 首先明确，前序+后序遍历的组合不能还原一棵二叉树
- 后序遍历的最后一个点是根节点，参照此根节点可以将中序遍历数组分成左右两部分，分别为左子树和右子树
- 依据以上思路递归重建二叉树
完整代码
# 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 inorder:
index = inorder.index(postorder.pop())
root = TreeNode(inorder[index])
root.right = self.buildTree(inorder[index+1:], postorder)
root.left = self.buildTree(inorder[:index], postorder)
return root
