题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

// 递归建立二叉树
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* root = NULL;
        root = build(preorder, inorder);
        return root;
    }

    TreeNode* build(vector<int> x, vector<int> z) {
        if(x.size() == 0) return NULL;

        TreeNode *root = new TreeNode(x[0]);
        x.erase(x.begin());

        vector<int> xl, xr, zl, zr;

        for(int i = 0; i < z.size(); i++) {

            if(z[i] == root->val) break;
            zl.push_back(z[i]);
        }

        for(int i = zl.size() + 1; i < z.size(); i++) {
            zr.push_back(z[i]);
        }

        for(int i = 0; i < zl.size(); i++) {
            xl.push_back(x[i]);
        }

        for(int i = xl.size(); i < x.size(); i++) {
            xr.push_back(x[i]);
        } 

        root->left = build(xl, zl);
        root->right = build(xr, zr);

        return root;
    }
};