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

中序遍历: 左 -> 根 -> 又 后序遍历: 左 -> 右 -> 根 则后序遍历的最后一个节点为根节点,该节点在中序数组中的索引 idx 的左侧即为左子树[0:idx],右侧为右子树 [idx + 1:]，该索引代表了左子树的长度,在后序数组中左子树为[0:idx],右子树为[idx:-1],从上至下建立树

# 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
        if not inorder or not postorder:
            return None
        root = TreeNode(postorder[-1])
        idx = inorder.index(postorder[-1])
        root.left = self.buildTree(inorder[:idx], postorder[:idx])
        root.right = self.buildTree(inorder[idx + 1:], postorder[idx: -1])
        return root