难度: Medium
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 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]
提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历运行时间: 232 ms
内存: 19.2 MB
# 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]) -> TreeNode:
def build(pstart, pend, istart, iend):
if pstart > pend:
return
root_val = postorder[pend]
root = TreeNode(root_val)
index = istart
for i in range(istart, iend+1):
if inorder[i] == root_val:
index = i
break
left_length = index - istart
root.left = build(pstart, pstart+left_length-1, istart, index-1)
root.right = build(pstart+left_length, pend-1, index+1, iend)
return root
return build(0, len(inorder)-1, 0, len(inorder)-1)
这个题解采用了分治的思想来递归构建二叉树。从后序遍历的最后一个元素可以确定根节点，然后在中序遍历中找到根节点的位置，从而确定左右子树的节点数量。递归对左右子树进行同样的构建过程，直到所有节点都加入二叉树。
时间复杂度: O(n^2)
空间复杂度: O(n)
```python
# 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]) -> TreeNode:
def build(pstart, pend, istart, iend):
if pstart > pend:
return
# 后序遍历的最后一个元素即为根节点
root_val = postorder[pend]
root = TreeNode(root_val)
# 在中序遍历中查找根节点的位置
index = istart
for i in range(istart, iend+1):
if inorder[i] == root_val:
index = i
break
# 左子树节点数量
left_length = index - istart
# 递归构建左子树
root.left = build(pstart, pstart+left_length-1, istart, index-1)
# 递归构建右子树
root.right = build(pstart+left_length, pend-1, index+1, iend)
return root
return build(0, len(inorder)-1, 0, len(inorder)-1)
```
在后序遍历中，根节点总是位于遍历序列的最后位置，这样可以直接确定根节点，而无需额外搜索。前序遍历的首元素同样是根节点，也可以用来确定根，但在结合中序遍历数据重构树的情景下，后序遍历提供了从树的底部向上构建树的直观顺序，这在递归构建时尤其有用。中序遍历序列中，根节点位置不固定，不能直接使用，必须通过其他方式确定根节点位置。
理论上，本算法假设树中没有重复元素。如果中序和后序遍历序列中存在重复元素，将无法准确地通过值来定位根节点在中序遍历中的位置，因为可能出现多个相同的值。这会导致重建的二叉树结构可能不正确。处理带有重复元素的树，需要其他数据结构或附加信息来唯一确定节点位置。
在递归过程中，首先通过后序遍历确定根节点，然后在中序遍历中找到根节点的位置，这个位置将中序序列分为左右两部分，分别对应左右子树的中序序列。左子树的节点数量即为根节点在中序遍历中的索引减去左边界索引。这个数量用于在后序遍历中确定左子树的边界。具体来说，如果根节点在中序遍历中的位置为index，左边界为istart，则左子树的节点数量为index-istart，这个值用来确定后序遍历中左子树节点的结束位置，从而形成左子树的后序序列。递归调用时，左子树的后序遍历范围是从当前后序起始到当前后序起始加上左子树长度减一，左子树的中序遍历范围是从当前中序起始到根节点索引减一。右子树的边界由剩余的部分确定。