重建二叉树
- 题目描述
- 题解
- 原理
- 代码
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
题解
原理
代码
TreeNode* build_tree(vector<int> preorder, vector<int> inorder) {unordered_map<int, int> number_index;int length = inorder.size();for (int i = 0; i < length; i++) {number_index[inorder[i]] = i;} // i:当前子树的前序遍历序列的起始位置。// j:当前子树的中序遍历序列的起始位置。std::function<TreeNode*(int, int, int)> handle = [&](int start_pre, int start_in, int length) -> TreeNode* {if (length < 1) return nullptr;int k = number_index[preorder[start_pre]];// l: 当前子树的左子树的节点数量int l = k - start_in;TreeNode* root = new TreeNode(preorder[start_pre]);root->left = handle(start_pre + 1, start_in, l);root->right = handle(start_pre + 1 + 1, start_in + 1, length - l - 1);};return handle(0, 0, length);}