C++刷剑指offer(面试题07. 重建二叉树)【递归】
本帖最后由 糖逗 于 2020-5-8 17:30 编辑题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder =
中序遍历 inorder =
返回如下的二叉树：
3
/ \
920
/\
15 7
限制：
0 <= 节点个数 <= 5000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <iostream>
#include <vector>
#include<math.h>
using namespace std;
struct TreeNode{
int val;
TreeNode*left;
TreeNode*right;
TreeNode(int x):val(x), left(NULL), right(NULL){
}
};
void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
if(root == NULL) return;
int insert = left + (right - left) / 2;
res = root->val;
middle(root->left, res, left, insert - 1, depth + 1);
middle(root->right, res, insert + 1, right, depth + 1);
}
int treeDepth(TreeNode* root){
if(root == NULL || root -> val == 0) return 0;
return max(treeDepth(root->left), treeDepth(root->right))+1;
}
void PrintTree(TreeNode* root) {
int depth = treeDepth(root);
cout << "depth:" << depth << endl;
int width = pow(2, depth) - 1;
vector<vector<int> > res(depth, vector<int>(width, 0));
middle(root, res, 0, width - 1, 0);
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < res.size();j++){
if(res == 0){
cout<< " ";
}
else{
cout << res;
}
}
cout << endl;
}
cout << "------------------" << endl;
}
TreeNode* Create(vector<int>& preorder, vector<int>& inorder, int start, int now, int end){
if(start > end) return NULL;
TreeNode* node = new TreeNode(preorder);
int i = start;
while(i < end &&inorder != preorder) i++;
node -> left = Create(preorder, inorder, start, now+1, i-1);
node -> right = Create(preorder, inorder, i+1, now + i + 1 - start, end);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
TreeNode* tree = Create(preorder, inorder, 0, 0, preorder.size()-1);
returntree;
}
int main(void){
cout << "please send numbers for perorder" << endl;
vector<int> perorder, inorder;
int number1, number2;
while(cin >> number1){
perorder.push_back(number1);
}
cin.clear();
cout << "please send numbers for inorder" << endl;
while(cin >> number2){
inorder.push_back(number2);
}
TreeNode* tree = buildTree(perorder, inorder);
PrintTree(tree);
return 0;
}
注意事项：
1.边界确定，这里now + i + 1 - start必须加start，因为每一次迭代左边界start都在变化，这里不能简单的将start与0等价。
2.参考链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/er-cha-shu-de-qian-xu-bian-li-fen-zhi-si-xiang-by-/
页:
[1]