力扣题目：
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
思路：
找到根节点：
后序遍历数组的最后一个元素是树的根节点。这里 postorder 的最后一个元素是 3，所以根节点是 3。
匹配和切割：
在中序遍历数组中找到根节点 3 的位置。inorder 数组中，3 的位置是第 1 个。
以 3 为界将 inorder 数组分割为左子树和右子树部分：
左子树部分为 [9]。
右子树部分为 [15, 20, 7]。
根据左子树和右子树的大小分割 postorder 数组：
左子树部分为 [9]，大小为 1。
右子树部分为 [15, 7, 20]，大小为 3。
迭代过程：
使用一个栈来帮助构建二叉树。将根节点 3 压入栈中。
遍历 postorder 数组的元素，从倒数第二个元素开始。
根据 postorder 和 inorder 的索引关系确定节点的左右子树。
以inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]为例：
初始化：
postorder = [9, 15, 7, 20] （移除了根节点 3）
创建根节点 TreeNode(3)，并将其压入栈中。
栈状态：[3]
处理右子树：
处理 postorder 的倒数第二个元素 20。
20 在 inorder 数组中的位置是 3，它在根节点 3 的右边，因此是右子树。
创建右子节点 TreeNode(20)，并将其压入栈中。
栈状态：[3, 20]
postorder = [9, 15, 7]
继续处理右子树：
处理 postorder 的倒数第三个元素 7。
7 在 inorder 数组中的位置是 4，它在 20 的右边，因此是右子树。
创建右子节点 TreeNode(7)，并将其压入栈中。
栈状态：[3, 20, 7]
postorder = [9, 15]
处理右子树的左子树：
处理 postorder 的倒数第四个元素 15。
15 在 inorder 数组中的位置是 2，它在 20 的左边，因此是左子树。
弹出栈顶节点直到找到合适的父节点。
创建左子节点 TreeNode(15)，并将其压入栈中。
栈状态：[3, 20, 15]
postorder = [9]
处理左子树：
处理 postorder 的倒数第五个元素 9。
9 在 inorder 数组中的位置是 0，它在 3 的左边，因此是左子树。
弹出栈顶节点直到找到合适的父节点。
创建左子节点 TreeNode(9)，并将其压入栈中。
栈状态：[3, 9]
postorder = []（后序遍历数组已经处理完）
通过上述过程，我们构建出了完整的二叉树。
完整代码如下：
/**
* 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) {
if (inorder.empty() || postorder.empty()) return nullptr;
// 创建一个哈希表，存储中序遍历中每个值的索引
unordered_map<int, int> inorderIndexMap;
for (int i = 0; i < inorder.size(); ++i) {
inorderIndexMap[inorder[i]] = i;
}
// 初始化根节点
int postIndex = postorder.size() - 1;
TreeNode* root = new TreeNode(postorder[postIndex--]);
// 使用栈来辅助构建二叉树
stack<TreeNode*> st;
st.push(root);
while (postIndex >= 0) {
TreeNode* node = st.top(); // 获取栈顶节点
int inIndex = inorderIndexMap[node->val]; // 获取当前节点在中序遍历中的索引
// 如果当前节点在中序遍历中的索引小于后续节点，则后续节点是右子节点
if (inIndex < inorderIndexMap[postorder[postIndex]]) {
node->right = new TreeNode(postorder[postIndex--]); // 创建右子节点
st.push(node->right); // 右子节点入栈
} else {
// 否则，处理左子树
while (!st.empty() && inorderIndexMap[st.top()->val] > inorderIndexMap[postorder[postIndex]]) {
node = st.top();
st.pop(); // 弹出栈顶节点，继续寻找父节点
}
node->left = new TreeNode(postorder[postIndex--]); // 创建左子节点
st.push(node->left); // 左子节点入栈
}
}
return root; // 返回构建的二叉树根节点
}
};
按照这个思路，可以做另一道类似的题：
105.从前序与中序遍历序列构造二叉树
题目代码如下：
/**
* 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>& preorder, vector<int>& inorder) {
// 创建一个哈希表存储每个值在中序遍历中的索引
unordered_map<int, int> inorderIndexMap;
for (int i = 0; i < inorder.size(); i++) {
inorderIndexMap[inorder[i]] = i;
}
// 用于跟踪前序遍历的当前索引
int preIndex = 0;
// 用前序遍历的第一个值初始化根节点
TreeNode* root = new TreeNode(preorder[preIndex++]);
// 使用一个栈来帮助构建树
stack<TreeNode*> st;
st.push(root);
// 遍历前序遍历的剩余部分
while (preIndex < preorder.size()) {
TreeNode* node = st.top();
int currentPreorderVal = preorder[preIndex];
int inIndex = inorderIndexMap[node->val];
int currentInorderIndex = inorderIndexMap[currentPreorderVal];
// 如果当前前序遍历的值在中序遍历中位于节点的左边，
// 这意味着我们仍然在遍历左子树。
if (currentInorderIndex < inIndex) {
node->left = new TreeNode(currentPreorderVal);
st.push(node->left);
} else {
// 否则，意味着我们需要添加一个节点到右子树。
while (!st.empty() && inorderIndexMap[st.top()->val] < currentInorderIndex) {
node = st.top();
st.pop();
}
node->right = new TreeNode(currentPreorderVal);
st.push(node->right);
}
preIndex++;
}
return root;
}
};
暂无评论