力扣：106. 从中序与后序遍历序列构造二叉树（Python3）

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

示例：

示例 1：

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

示例 2：

输入：inorder = [-1], postorder = [-1]
输出：[-1]

解法：

使用栈辅助（stack），栈中每个结点结构为[当前结点在中序序列中的下标, 树节点]，stack初始化的值是后序序列最后1个。

从后往前遍历后序序列， 从导数第2个开始。获取当前值在中序序列中的下标，如果比stack中最后1个大，说明当前结点是前个结点的右子树；否则需要弹出栈顶，直到比stack中最后1个小，此时说明当前结点是弹出结点的左子树。

知识点：

1.后序遍历：左-右-根。

代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        root = tree = TreeNode(postorder[-1])
        stack = [[inorder.index(postorder[-1]), tree]]
        for num in postorder[-2: -len(postorder) - 1: -1]:
            index = inorder.index(num)
            tree = TreeNode(num)
            if index > stack[-1][0]:
                stack[-1][1].right = tree
            else:
                while stack and index < stack[-1][0]:
                    pre = stack.pop()
                pre[1].left = tree
            stack.append([index, tree])
        return root