面试题 07. 重建二叉树
前中序构建
要根据二叉树的前序遍历和中序遍历结果来构建二叉树，我们可以利用以下性质：
- 前序遍历的第一个元素总是当前树的根节点。
- 中序遍历中，根节点将二叉树分为左子树和右子树。
思路
- 根据前序遍历的第一个元素确定根节点。
- 在中序遍历中找到根节点位置，这样可以确定左子树和右子树的元素。
- 递归地对左子树和右子树执行同样的操作，构建二叉树。
递归构建的步骤：
- 在前序遍历中，根节点是第一个元素。
- 找到这个根节点在中序遍历中的位置，左侧的所有元素属于左子树，右侧的所有元素属于右子树。
- 根据这个分割，递归构建左子树和右子树。
C++ 实现
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
// 哈希表用于快速查找中序遍历中根节点的位置
unordered_map<int, int> inorder_map;
// 构建二叉树函数
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 将中序遍历的值和它们对应的下标存入哈希表，便于快速查找根节点位置
for (int i = 0; i < inorder.size(); ++i) {
inorder_map[inorder[i]] = i;
}
return build(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}
private:
TreeNode* build(const vector<int>& preorder, int preStart, int preEnd, int inStart, int inEnd) {
// 如果已经没有节点需要构建，返回空
if (preStart > preEnd || inStart > inEnd) {
return nullptr;
}
// 前序遍历的第一个节点是当前树的根节点
int rootVal = preorder[preStart];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
int inRoot = inorder_map[rootVal];
// 左子树的节点数目
int leftTreeSize = inRoot - inStart;
// 递归构建左子树和右子树
root->left = build(preorder, preStart + 1, preStart + leftTreeSize, inStart, inRoot - 1);
root->right = build(preorder, preStart + leftTreeSize + 1, preEnd, inRoot + 1, inEnd);
return root;
}
};
// 测试函数
void printTree(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " "; // 打印根节点
printTree(root->left); // 递归打印左子树
printTree(root->right); // 递归打印右子树
}
int main() {
vector<int> preorder = {3, 9, 20, 15, 7}; // 前序遍历
vector<int> inorder = {9, 3, 15, 20, 7}; // 中序遍历
Solution sol;
TreeNode* root = sol.buildTree(preorder, inorder);
// 打印构建后的二叉树，前序遍历方式
printTree(root); // 输出: 3 9 20 15 7
return 0;
}
代码解析
-
哈希表优化：我们使用
unordered_map将中序遍历的每个值与它在数组中的位置进行映射，以便快速查找根节点在中序遍历中的位置，时间复杂度从 O(n) 降到 O(1)。 -
递归函数
build：preStart和preEnd分别表示前序遍历中当前子树的起始和结束位置。inStart和inEnd表示中序遍历中当前子树的起始和结束位置。- 每次从前序遍历中获取根节点，然后在中序遍历中找到这个根节点的位置，从而将左右子树分割开。
- 递归地构建左右子树。
-
时间复杂度：O(n)，因为每个节点都需要访问一次。
-
空间复杂度：O(n)，用于存储哈希表和递归调用栈。
测试输出
对于输入的前序遍历 [3, 9, 20, 15, 7] 和中序遍历 [9, 3, 15, 20, 7]，构建出的二叉树结构如下：
3
/ \
9 20
/ \
15 7
输出的前序遍历为：3 9 20 15 7，与原始前序遍历一致，说明二叉树构建正确。
中后序构建
使用中序遍历和后序遍历结果构建二叉树的过程与前序和中序构建类似，不过需要注意：
- 在后序遍历中，最后一个元素是当前树的根节点。
- 在中序遍历中，根节点将二叉树分为左子树和右子树。
- 递归地对左子树和右子树执行同样的操作，构建二叉树。
构建步骤
- 后序遍历的最后一个元素即为当前树的根节点。
- 在中序遍历中找到根节点的位置，从而将左子树和右子树分开。
- 递归地构建左右子树。
C++ 实现
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
unordered_map<int, int> inorder_map; // 哈希表存储中序遍历的索引，方便查找
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 存储中序遍历值对应的索引
for (int i = 0; i < inorder.size(); ++i) {
inorder_map[inorder[i]] = i;
}
return build(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
}
private:
TreeNode* build(const vector<int>& inorder, const vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd) {
// 递归终止条件
if (inStart > inEnd || postStart > postEnd) {
return nullptr;
}
// 后序遍历的最后一个元素是根节点
int rootVal = postorder[postEnd];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历中找到根节点的位置
int inRoot = inorder_map[rootVal];
int leftTreeSize = inRoot - inStart; // 左子树的节点数目
// 递归构建左子树和右子树
root->left = build(inorder, postorder, inStart, inRoot - 1, postStart, postStart + leftTreeSize - 1);
root->right = build(inorder, postorder, inRoot + 1, inEnd, postStart + leftTreeSize, postEnd - 1);
return root;
}
};
// 打印树的前序遍历
void printPreOrder(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
printPreOrder(root->left);
printPreOrder(root->right);
}
int main() {
vector<int> inorder = {9, 3, 15, 20, 7}; // 中序遍历
vector<int> postorder = {9, 15, 7, 20, 3}; // 后序遍历
Solution sol;
TreeNode* root = sol.buildTree(inorder, postorder);
// 输出前序遍历的结果，以检查树是否构建正确
printPreOrder(root); // 输出: 3 9 20 15 7
return 0;
}
代码解析
-
构建哈希表：
- 使用
unordered_map存储中序遍历中每个值的索引，方便快速找到根节点在中序遍历中的位置。
- 使用
-
递归构建函数
build：inStart和inEnd表示当前子树在中序遍历中的范围。postStart和postEnd表示当前子树在后序遍历中的范围。- 从后序遍历的最后一个元素获取根节点，并在中序遍历中找到该节点的位置，进而划分左右子树。
- 递归调用
build分别构建左右子树。
-
测试：
- 构建的树结构：
3 / \ 9 20 / \ 15 7 - 使用前序遍历打印输出：
3 9 20 15 7，验证构建的树结构正确。
- 构建的树结构：
复杂度分析
- 时间复杂度：O(n)，遍历所有节点，并在哈希表中查找根节点索引的操作是 O(1)。
- 空间复杂度：O(n)，用于存储哈希表和递归调用栈。
层序编列
1
/ \
2 3
\ / \
4 5 6
面试题 09. 用两个栈实现队列
这个问题可以用两个栈来实现，用一个栈保存归还的书籍（push 操作），而借出书籍时（pop 操作）可以通过另一个栈来保证借出的是最早归还的书。具体思路如下：
- 使用两个栈
stack1和stack2。stack1用于存放归还的书籍，stack2用于按顺序借出书籍。 push操作：直接将书籍编号压入stack1。pop操作：如果stack2为空，则将stack1中的所有元素依次弹出并压入stack2，这样最早归还的书会在stack2的顶部。然后从stack2弹出顶部的元素，返回该书籍编号。
在实现中，这种方式保证了最早归还的书优先借出。
以下是 C++ 代码：
#include <stack>
class BookQueue {
private:
std::stack<int> stack1; // 用于归还书籍
std::stack<int> stack2; // 用于借出书籍
public:
BookQueue() {}
void push(int bookID) {
stack1.push(bookID);
}
int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
if (stack2.empty()) {
return -1; // 没有书可以借出
}
int bookID = stack2.top();
stack2.pop();
return bookID;
}
};
示例
BookQueue bookQueue;
bookQueue.push(1); // 书队列为 [1]
bookQueue.push(2); // 书队列为 [1, 2]
std::cout << bookQueue.pop(); // 返回 1，书队列变为 [2]
解释
push操作只涉及stack1，时间复杂度为 (O(1))。pop操作在stack2不为空时为 (O(1))；如果stack2为空时，则需要将stack1的元素移动到stack2中，平均时间复杂度仍为 (O(1))。
这样，我们就可以实现按照顺序的借书和还书功能了。