1.题目
这道题是2024-2-21的签到题，题目难度为中等。
考察知识点为递归。
题目链接：从中序与后序遍历序列构造二叉树
给定两个整数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
2.思路
这道题其实思路和昨天题目差不多，如果没看过我昨天的题目解析的朋友可以参考下这个：
从前序与中序遍历序列构造二叉树
多余的废话我也就不多说了，下面是我这道题的核心思想：
构建递归函数
首先是需要定义一个递归函数用于构建树，这里的树是针对所有具有树结构的，大至以root结点为根节点的整棵树，小至叶子节点这颗特殊的树（没有左右结点，其实结点可以看着一个特殊的子树），而构建树我们最需要确定的是它结点的中序遍历结果和后序遍历值，因此我们需要传入4个参数：
p_start：当前树的后序遍历开始索引
p_end：当前树的后序遍历结束索引
i_start：当前树的中序遍历开始索引
i_end：当前树的中序遍历结束索引
递归终止条件
确定了递归函数的参数和意义后，我们需要确定递归终止条件，很明显，这个条件肯定和我们传入的参数有关，根据上面的4个参数我们可以知道一个树的遍历数组范围长度肯定是大于0的，而它的遍历数组长度由起始索引和终止索引决定，因此对于任意一个遍历数组，它的start必须小于end。于是我们可以定义递归终止条件是，当start > end，则返回None，否则则继续执行构建逻辑。
如果满足上述条件，我们需要开始构建树的逻辑了，首先我们获取当前树的根节点值，这个我们可以从后序遍历数组和后序遍历结束索引来找，因为后序遍历数组的值肯定满足下面这个：
[(左子树的所有结点值)，(右子树的所有结点值)，根节点值]
找到了根节点的值之后，我们利用python的index函数来找当前根节点值在当前的中序遍历数组索引值，从而得到当前树的左子结点数量和右子结点数量。
左右子树参数公式推导
做完上述构建准备后，我们首先构建树的根节点，将当前树的root值传入类中并构建结点，然后递归构建它的左右子结点（其实可以看作是左右子树的两个根节点），两颗子树的4个构建参数肯定满足下面公式
左子树参数推导
右子树参数推导
3.代码
# 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]:
# 计算当前遍历数组的长度
length = len(inorder)
def build(i_start,i_end,p_start,p_end):
# 如果开始坐标索引 > 结束坐标索引
if i_start > i_end:
return None
# 根节点在中序遍历数组的下标索引
ino_rootIndex = inorder.index(postorder[p_end])
# 当前树的左子树所有结点个数
leftNum = ino_rootIndex - i_start
# 当前树的右子树所有结点个数
rightNum = i_end - ino_rootIndex
# 构建当前树的根节点
root = TreeNode(postorder[p_end])
# 递归构建当前树的左子树
root.left = build(i_start,ino_rootIndex-1,p_start,p_start+leftNum-1)
# 递归构建当前树的右子树
root.right = build(ino_rootIndex+1,i_end,p_start+leftNum,p_end-1)
# 返回当前树的根节点
return root
return build(0,length-1,0,length-1)
