106. 从中序与后序遍历序列构造二叉树
示例 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]
思路：后序数组最后一个值是当前的中间节点，以后序数组的最后一个值对中序数组进行分割，分成左子树（左中序数组），右子树（右中序数组）。
对于后序数组，先去掉最后一个元素，然后根据左中序数组的大小对后序数组进行分割，分割为左后序数组和右后序数组。
最后递归的去找当前节点左子树的中间节点，右子树的中间节点。
代码：
class Solution { //106. 从中序与后序遍历序列构造二叉树
public:
TreeNode* traversal(vector& inorder, vector& postorder) {
if (postorder.size() == 0) return nullptr;
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue); //中间节点
if (postorder.size() == 1) return root; //叶子节点
//找中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); ++delimiterIndex) {
if (inorder[delimiterIndex] == rootValue) break;
}
//切割中序数组，左闭右开区间
vector leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
vector rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());
//后序数组，去掉最后一个
postorder.pop_back();
//切割后序数组
vector leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
vector rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
TreeNode* buildTree(vector& inorder, vector& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return nullptr;
return traversal(inorder, postorder);
}
};
参考资料：代码随想录
