重建二叉树

C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2022-02-10

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int vinlen = vin.size();
        if(vinlen == 0)
            return NULL;
        vector<int> pre_left, pre_right, vin_left, vin_right;
        //创建根节点
        TreeNode* root = new TreeNode(pre[0]);
        //找到根节点再中序遍历中的位置
        int gen = 0;
        for(int i = 0; i < vinlen; i++){
            if(vin[i] == pre[0]){
                gen = i;
                break;
            }
        }
        //找到在左边的结点
        for(int i = 0; i < gen; i++){
            vin_left.push_back(vin[i]);
            pre_left.push_back(pre[i+1]);
        }
        //找到在右边的结点
        for(int i = gen + 1; i < vinlen; i++){
            vin_right.push_back(vin[i]);
            pre_right.push_back(pre[i]);
        }
        //递归,利用返回值来插入，妙的离谱
        root->left = reConstructBinaryTree(pre_left, vin_left);
        root->right = reConstructBinaryTree(pre_right, vin_right);
        return root;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2021-10-25

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
       if(pre.size()==0) return nullptr;
       TreeNode* root = new TreeNode(pre[0]);
       int i = 0;
       for(;i<=pre.size();i++){
           if (pre[0] == vin[i]) break;
       }
       vector< int > lowin(vin.begin(),vin.begin()+i);
       vector< int > highin(vin.begin()+i+1,vin.end());
       vector< int > lowpre(pre.begin()+1,pre.begin()+lowin.size()+1);
       vector< int > highpre(pre.begin()+lowin.size()+1,pre.end());
       root->left = reConstructBinaryTree(lowpre,lowin);
       root->right = reConstructBinaryTree(highpre,highin);
       return root;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2021-09-14

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
	TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
	{
        if ((pre.empty()) || (vin.empty())) {
            return nullptr;
        }
		int rootVal = pre[0];
        int midPos = find(vin.begin(), vin.end(), rootVal) - vin.begin();
        // 中序遍历左右子树
        vector<int> newVinLeft(vin.begin(), vin.begin() + midPos);
        vector<int> newVinRight(vin.begin() + midPos + 1, vin.end());
        // 前序遍历左右子树
        vector<int> newPerLeft(pre.begin() + 1, pre.begin() + 1 + newVinLeft.size());
        vector<int> newPerRight(pre.begin() + 1 + newVinLeft.size(), pre.end());
        // 创建根节点
        TreeNode *root = new TreeNode(rootVal);
        root->left = reConstructBinaryTree(newPerLeft, newVinLeft);
        root->right = reConstructBinaryTree(newPerRight, newVinRight);
        return root;
	}
};

C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2021-09-13

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> p, v;
    
    TreeNode* build(int l1, int r1, int l2, int r2) {
        if (l1 > r1) return nullptr;
        
        TreeNode* root = new TreeNode(p[l1]);
        int temp = l2;
        while (temp <= r2) {
            if (v[temp] == p[l1]) break;
            temp++;
        }
        root->left = build(l1 + 1, l1 + temp - l2, l2, temp - 1);
        root->right = build(l1 + temp - l2 + 1, r1, temp + 1, r2);
        
        return root;
    }
    
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int len = pre.size();
        if (!len || len != vin.size()) return nullptr;
        
        p = pre;
        v = vin;
        TreeNode* root = build(0, len - 1, 0, len - 1);
        
        return root;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2021-09-13

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* Tree(vector<int>& pre,int preStart,int preEnd,vector<int>& vin,int vinStart, int vinEnd)
    {
        if(preStart > preEnd)
        {
            return nullptr;
        }
        int rootValue = pre[preStart];
        int index = 0;
        for(int i = vinStart; i <= vinEnd;++i)
        {
            if(vin[i] == rootValue)
            {
                index = i;
                break;
            }
        }
        int leftsize = index - vinStart;
        TreeNode* root = new TreeNode(rootValue);
        root->left = Tree(pre,preStart+1,preStart+leftsize,vin,vinStart,index-1);
        root->right = Tree(pre,preStart+leftsize+1,preEnd,vin,index+1,vinEnd);
        return root;
    }
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        return Tree(pre,0,pre.size()-1,vin,0,vin.size()-1);
    }
    
};

详情