题目描述
考研题
重建二叉树
输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。
输出层序遍历,二叉树空节点输出null
重建二叉树
#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
// 前序遍历第一个是根节点,在中序遍历根节点左边是左子树(left_subtree_len),右边是右子树(right_subtree_len)
// 根节点后长度为(len_subtree_len)的为左子树的前序遍历,后边长度为(right_subtree_len)为右子树的前序遍历
// 这里就能看出递归了,状态变量包括5个:前序遍历头节点,前序遍历尾节点,中序遍历头节点,中序遍历尾节点,长度
// 已知头节点和尾节点的索引,长度可以被省略,由于都需要数数组,可以设置为全局
// 由于需要找到中序遍历中根节点的位置,所以记录每个结点在中序遍历序列中的位置
unordered_map<int, int> node_to_inorder_id;
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
int n = preorder.size();
for (int i = 0; i < n; i++)
{
node_to_inorder_id[inorder[i]] = i;
}
return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
}
TreeNode *dfs(vector<int> &preorder, vector<int> &inorder, int pre_l, int pre_r, int in_l, int in_r) // 函数的返回依据记录路径的方式
{
// 如果达到递归中止条件就return
if (pre_l > pre_r)
return NULL;
// 如果是目标状态就输出或者记录路径
// 该题并没有目标状态,而是直到触发递归终止条件
// 如果未达目标状态,就切换状态变量
int root_val = preorder[pre_l];
TreeNode *root = new TreeNode(root_val);
int inorder_root_id = node_to_inorder_id[root_val];
int left_subtree_len = inorder_root_id - in_l;
root->left = dfs(preorder, inorder, pre_l + 1, pre_l + left_subtree_len, in_l, inorder_root_id - 1);
root->right = dfs(preorder, inorder, pre_l + left_subtree_len + 1, pre_r, inorder_root_id + 1, in_r);
return root;
}
};
int main()
{
Solution solution;
vector<int> preorder = {3, 9, 20, 15, 7};
vector<int> inorder = {9, 3, 15, 20, 7};
TreeNode *root = solution.buildTree(preorder, inorder);
// 层序遍历,即广度优先搜索
queue<TreeNode *> q;
q.push(root);
while (!q.empty())
{
TreeNode *node = q.front();
q.pop();
if (node == NULL)
{
cout << "null ";
continue;
}
cout << node->val << " ";
q.push(node->left);
q.push(node->right);
}
cout << endl;
return 0;
}