176.二叉树：从中序与后序遍历序列构造二叉树（力扣）

代码解决

/*** 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, vector<int>& postorder) {// 如果后序遍历序列为空，返回空指针if (postorder.size() == 0) return nullptr;// 获取后序遍历序列的最后一个值作为当前子树的根节点值int rootVal = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(rootVal);// 如果后序遍历序列只有一个值，返回根节点if (postorder.size() == 1) return root;// 在中序遍历序列中找到根节点值的位置int delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootVal)break;}// 划分左子树和右子树的中序遍历序列vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());// 移除后序遍历序列的最后一个元素postorder.resize(postorder.size() - 1);// 划分左子树和右子树的后序遍历序列vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());// 递归构建左子树和右子树root->left = traversal(leftInorder, leftPostorder);root->right = traversal(rightInorder, rightPostorder);// 返回构建好的根节点return root;}// 主函数，从中序和后序遍历序列中构建二叉树TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {// 如果中序或后序遍历序列为空，返回空指针if (inorder.size() == 0 || postorder.size() == 0) return nullptr;// 调用递归函数构建二叉树return traversal(inorder, postorder);}
};

1. 定义一个递归函数 traversal，它接受中序遍历序列和后序遍历序列作为参数。
2. 首先检查后序遍历序列是否为空，如果是，返回空指针。
3. 获取后序遍历序列的最后一个值，这个值就是当前子树的根节点的值。
4. 在中序遍历序列中找到根节点值的位置，并将其作为分隔点，将中序遍历序列划分为左子树和右子树的中序遍历序列。
5. 移除后序遍历序列的最后一个元素，并将其作为分隔点，将后序遍历序列划分为左子树和右子树的后序遍历序列。
6. 递归地调用 traversal 函数来构建左子树和右子树。
7. 返回构建好的根节点。
8. 在 buildTree 函数中，首先检查中序或后序遍历序列是否为空，如果是，返回空指针。然后调用 traversal 函数来构建二叉树。

这个算法的时间复杂度是 O(n)，因为每个节点都会被访问一次，其中 n 是树中节点的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。