从中序与后序遍历序列构造二叉树Python解法_python给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
 

例：

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

解析：

后序遍历的最后一个值即为根节点，在中序遍历中找到该值，在中序遍历中，该值得左边为左子树，右边为右子树，每次遍历可以确定一个值，即根节点。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        def build(pos_left, pos_right, mid_left, mid_right):
            if pos_left > pos_right or mid_left > mid_right:  # 停止条件 
                return None
            root = TreeNode(postorder[pos_right])  # 构建节点
            mid_root = mid_left
            while mid_root <= mid_right and inorder[mid_root] != postorder[pos_right]:  #找寻根节点
                mid_root += 1
            diff = mid_root - mid_left  # 左子树的长度
            root.left = build(pos_left, pos_left + diff -1, mid_left, mid_root - 1)  # 构建左子树
            root.right = build(pos_left + diff, pos_right - 1, mid_root + 1, mid_right)  # 构建右子树
            return root  # 返回构建好的树
        return build(0, len(postorder) - 1, 0, len(inorder) - 1)