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

糖逗

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

 

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   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[depth][insert] = 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[i].size();j++){
                if(res[i][j] == 0){
                        cout  << " ";
                }
                else{
                        cout << res[i][j];
                }
               
        }
        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[now]);
        int i = start;
        while(i < end &&inorder[i] != preorder[now]) 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);
         return  tree;
        
}





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 ... n-zhi-si-xiang-by-/