【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致)
【题目描述】
给定两个整数数组 inorder
和 postorder
,其中 inorder
是二叉树的中序遍历, postorder
是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
【示例一】
输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出:[3,9,20,null,null,15,7]
【示例二】
输入:inorder = [-1], postorder = [-1] 输出:[-1]
【提示及数据范围】
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder
和postorder
都由 不同 的值组成postorder
中每一个值都在inorder
中inorder
保证是树的中序遍历postorder
保证是树的后序遍历
【代码】
// 方法一:递归
class Solution {
int post_idx;
unordered_map<int, int> idx_map;
public:
TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
// 如果这里没有节点构造二叉树了,就结束
if (in_left > in_right) {
return nullptr;
}
// 选择 post_idx 位置的元素作为当前子树根节点
int root_val = postorder[post_idx];
TreeNode* root = new TreeNode(root_val);
// 根据 root 所在位置分成左右两棵子树
int index = idx_map[root_val];
// 下标减一
post_idx--;
// 构造右子树
root->right = helper(index + 1, in_right, inorder, postorder);
// 构造左子树
root->left = helper(in_left, index - 1, inorder, postorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 从后序遍历的最后一个元素开始
post_idx = (int)postorder.size() - 1;
// 建立(元素,下标)键值对的哈希表
int idx = 0;
for (auto& val : inorder) {
idx_map[val] = idx++;
}
return helper(0, (int)inorder.size() - 1, inorder, postorder);
}
};
// 方法二:迭代
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0) {
return nullptr;
}
auto root = new TreeNode(postorder[postorder.size() - 1]);
auto s = stack<TreeNode*>();
s.push(root);
int inorderIndex = inorder.size() - 1;
for (int i = int(postorder.size()) - 2; i >= 0; i--) {
int postorderVal = postorder[i];
auto node = s.top();
if (node->val != inorder[inorderIndex]) {
node->right = new TreeNode(postorderVal);
s.push(node->right);
} else {
while (!s.empty() && s.top()->val == inorder[inorderIndex]) {
node = s.top();
s.pop();
inorderIndex--;
}
node->left = new TreeNode(postorderVal);
s.push(node->left);
}
}
return root;
}
};