/**
* 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* traversal(vector<int>& inorder, int iBegin, int iEnd, vector<int>& postorder, int pBegin, int pEnd) {
// 每次从后序遍历查找中节点,在这之前需要判断后序遍历是否还有值
if(pBegin == pEnd) return NULL;
// 建立中节点
int rootValue = postorder[pEnd - 1];
auto root = new TreeNode(rootValue);
// 分割中序遍历,统一使用左闭右开
int index;
for(index = iBegin; index < iEnd; index++) {
if(inorder[index] == rootValue) break;
}
// 中序遍历分割左子树区间
int leftIBegin = iBegin;
int leftIEnd = index; // 右边是开,所以这里并不包含 inorder[index]
// 右子树区间
int rightIBegin = leftIEnd + 1;
int rightIEnd = iEnd;
// 统一使用左闭右开
// 分割后序遍历,只需要根据中序遍历分割出的左子树长度和右子树长度来切割即可
int leftPBegin = pBegin;
int leftPEnd = leftPBegin + (leftIEnd - leftIBegin);
int rightPBegin = leftPEnd;
// 因为是右开区间,所以已经自动去掉末尾的中节点
int rightPEnd = rightPBegin + (rightIEnd - rightIBegin);
// 递归子树
root->left = traversal(inorder, leftIBegin, leftIEnd, postorder, leftPBegin, leftPEnd);
root->right = traversal(inorder, rightIBegin, rightIEnd, postorder, rightPBegin, rightPEnd);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(!inorder.size() || !postorder.size()) return NULL;
// 左闭右开
return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
};