题目描述

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:
    vector<int> preorder_ , inorder_;
    unordered_map<int,int> hash;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        preorder_ = preorder;
        inorder_ = inorder;
        if(!preorder_.size() || !inorder_.size() || preorder_.size() != inorder_.size())
            return nullptr;
        for(int i = 0 ; i < inorder_.size() ; i++){
            hash[inorder_[i]] = i;
        }

        return dfs(0 , preorder_.size() - 1  , 0 , inorder_.size() - 1);

    }

    TreeNode* dfs(int prel , int prer , int inl , int inr){
        if(prel > prer) return nullptr;

        TreeNode *head = new TreeNode(preorder_[prel]);
        // 头结点值在中序遍历中的下标
        int k = hash[preorder_[prel]];
        // k -inl 表示在中序遍历中该head结点左子树的宽度
        head->left = dfs(prel + 1, prel + k - inl  ,inl , k - 1);
        head->right = dfs(prel + k - inl + 1, prer , k + 1 , inr);

        return head;
    }
};