题解 | 从中序与后序遍历序列构造二叉树

分治法：将原问题分解成若干个规模较小的子问题，这些子问题的结构与原问题相似。通常，子问题是相互独立的，并且问题规模通常比原问题小。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param inorder int整型一维数组 中序遍历序列
# @param postorder int整型一维数组 后序遍历序列
# @return TreeNode类
#
class Solution:
    def buildTree(self , inorder: List[int], postorder: List[int]) -> TreeNode:
        # write code here
        #insight: 中序遍历，左->根->右；后序遍历，左->右->根；
        #可以推断出后序遍历的最后一个节点为根节点，又由于节点的值各不相同，
        #在中序遍历序列中查找此节点，得到索引i，i的左侧为左子树[0:i],右侧为右子树[i+1:]
        #在后序遍历序列中，左子树为[0:i],右子树为[i:-1]
        if not inorder: #有左子树但右子树为空，构建root.right时; 或反之,构建root.left时
            return None
        elif len(inorder)==1:
            return TreeNode(inorder[0])
        root_val=postorder[-1]
        root=TreeNode(root_val)
        i=inorder.index(root_val)
        root.left= self.buildTree(inorder[0:i],postorder[0:i])
        root.right= self.buildTree(inorder[i+1:],postorder[i:-1])
        return root