C++刷剑指offer(面试题07. 重建二叉树)【递归】

糖逗

题目描述：

1. 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
   
2. 
   
3.  
   
4. 
   
5. 例如，给出
   
6. 
   
7. 前序遍历 preorder = [3,9,20,15,7]
   
8. 中序遍历 inorder = [9,3,15,20,7]
   
9. 返回如下的二叉树：
   
10. 
    
11.     3
    
12.    / \
    
13.   9  20
    
14.     /  \
    
15.    15   7
    
16.  
    
17. 
    
18. 限制：
    
19. 
    
20. 0 <= 节点个数 <= 5000
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include<math.h>
   
4. 
   
5. using namespace std;
   
6. 
   
7. 
   
8. struct TreeNode{
   
9.         int val;
   
10.         TreeNode*left;
    
11.         TreeNode*right;
    
12.         TreeNode(int x):val(x), left(NULL), right(NULL){
    
13.         }
    
14. };
    
15. 
    
16. 
    
17. void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
    
18.     if(root == NULL) return;
    
19.     int insert = left + (right - left) / 2;
    
20.     res[depth][insert] = root->val;
    
21.            
    
22.     middle(root->left, res, left, insert - 1, depth + 1);
    
23.     middle(root->right, res, insert + 1, right, depth + 1);
    
24. }
    
25. 
    
26. int treeDepth(TreeNode* root){
    
27.     if(root == NULL || root -> val == 0) return 0;
    
28.    
    
29.     return max(treeDepth(root->left), treeDepth(root->right))+1;
    
30. }
    
31.       
    
32. void PrintTree(TreeNode* root) {
    
33.     int depth = treeDepth(root);
    
34.     cout << "depth:" << depth << endl;
    
35.     int width = pow(2, depth) - 1;
    
36.     vector<vector<int> > res(depth, vector<int>(width, 0));
    
37.     middle(root, res, 0, width - 1, 0);
    
38.     for(int i = 0; i < res.size(); i++){
    
39.         for(int j = 0; j < res[i].size();j++){
    
40.                 if(res[i][j] == 0){
    
41.                         cout  << " ";
    
42.                 }
    
43.                 else{
    
44.                         cout << res[i][j];
    
45.                 }
    
46.                
    
47.         }
    
48.         cout << endl;
    
49.     }
    
50.     cout << "------------------" << endl;
    
51. }
    
52. 
    
53. 
    
54. TreeNode* Create(vector<int>& preorder, vector<int>& inorder, int start, int now, int end){
    
55.         if(start > end) return NULL;
    
56.         TreeNode* node = new TreeNode(preorder[now]);
    
57.         int i = start;
    
58.         while(i < end &&inorder[i] != preorder[now]) i++;
    
59.         node -> left = Create(preorder, inorder, start, now+1, i-1);
    
60.         node -> right = Create(preorder, inorder, i+1, now + i + 1 - start, end);
    
61.         return node;
    
62. }
    
63. 
    
64. TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder){
    
65.          TreeNode* tree = Create(preorder, inorder, 0, 0, preorder.size()-1);
    
66.          return  tree;
    
67.        
    
68. }
    
69. 
    
70. 
    
71. 
    
72. 
    
73. 
    
74. int main(void){
    
75.         cout << "please send numbers for perorder" << endl;
    
76.         vector<int> perorder, inorder;
    
77.         int number1, number2;
    
78.         while(cin >> number1){
    
79.                 perorder.push_back(number1);
    
80.         }
    
81.         cin.clear();
    
82.         cout << "please send numbers for inorder" << endl;
    
83.         while(cin >> number2){
    
84.                 inorder.push_back(number2);
    
85.                
    
86.         }
    
87.        
    
88.         TreeNode* tree = buildTree(perorder, inorder);
    
89.         PrintTree(tree);
    
90.         return 0;
    
91. }
    

复制代码

注意事项：
1.边界确定，这里now + i + 1 - start必须加start，因为每一次迭代左边界start都在变化，这里不能简单的将start与0等价。
2.参考链接：https://leetcode-cn.com/problems ... n-zhi-si-xiang-by-/