题目
给定两个整数数组 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保证是树的后序遍历
解答
- 递归构造
根据题意，可以得知后序遍历的最后一个元素一定是树的根节点。然后可以在中序遍历中找到该根节点，以此将树分为左子树和右子树。对于左子树和右子树，可以再分别在中序遍历和后序遍历中找到其根节点，以此类推。
所以该问题可以使用递归的方式解决，每次递归时，先找到后序遍历的最后一个元素作为根节点，在中序遍历中找到该根节点，以此将树分为左子树和右子树。再分别递归左子树和右子树构建二叉树。C++代码实现如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 创建根节点
TreeNode* root = build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
return root;
}
TreeNode* build(vector<int>& inorder, int inStart, int inEnd, vector<int>& postorder, int postStart, int postEnd) {
/*
inorder：中序遍历序列；
postorder：后序遍历序列；
inStart：当前子树在中序遍历序列中的起始位置；
inEnd：当前子树在中序遍历序列中的结束位置；
postStart：当前子树在后序遍历序列中的起始位置；
postEnd：当前子树在后序遍历序列中的结束位置。
*/
// 特判： 若postStart > postEnd时， 无节点需要处理，返回NULL
if (postStart > postEnd) {
return nullptr;
}
// 创建新的子树根节点
TreeNode* root = new TreeNode(postorder[postEnd]); // 后续遍历的最后一个元素一定是根节点
// 在中序遍历中寻找当前子树根节点的位置
int inRootIndex = inStart;
while (inorder[inRootIndex] != root->val) {
inRootIndex++;
}
// 计算当前子树左子树的大小
int leftTreeSize = inRootIndex - inStart;
// 根据根节点的位置， 分别递归构建左子树和右子树
root->left = build(inorder, inStart, inRootIndex - 1, postorder, postStart, postStart + leftTreeSize - 1);
root->right = build(inorder, inRootIndex + 1, inEnd, postorder, postStart + leftTreeSize, postEnd - 1);
return root;
}
};关于root->left = build(inorder, inStart, inRootIndex - 1, postorder, postStart, postStart + leftTreeSize - 1);和root->right = build(inorder, inRootIndex + 1, inEnd, postorder, postStart + leftTreeSize, postEnd - 1); 的解释：
在中序遍历中找到了根节点的位置后，在中序遍历中根节点的左边就是左子树的中序遍历，根节点的右边就是右子树的中序遍历，在递归调用时，左子树的中序遍历的右边界指针指向根节点索引-1，同理右子树的中序遍历的左边界指针指向根节点索引+1；计算了左子树的大小之后，可以发现在后序遍历中，从最开始到左子树的大小-1的元素即为左子树对应的后序遍历，因此从最开始索引+左子树大小到最右边索引-1的后序遍历即为右子树的后序遍历，这样一直递归即可得到完整的左右子树，将子树同根节点连接，返回根节点即可得到完整的树。
在整个递归的过程中，我们都不需要额外的空间来存储子数组，而是通过起始和结束下标来表示子数组。这种方式使得我们可以使用较少的空间来解决问题，并且在递归过程中也不需要频繁地拷贝数组，提高了算法的效率。