这个BTree构造的算法，O(n)时间复杂度？

Question

给定一棵树的前序和中序遍历，构造二叉树。

注意： 您可以假设树中不存在重复项。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            
            if (preorder.empty()) return nullptr;
            

            TreeNode* root;
            
            //inorder val , index
            unordered_map<int, int> inOrderMap;
            unordered_map<int, int> preOrderMap;
            for (int i = 0; i < inorder.size(); i++) {
                preOrderMap.insert({preorder.at(i), i});
                inOrderMap.insert({inorder.at(i), i});
            }
            
            root = recursiveHelper(preorder, preOrderMap, inorder, inOrderMap, 0, inorder.size() - 1);
            
            return root;
        }
    
    private: 
        TreeNode* recursiveHelper(const vector<int>& preorder, 
                                  const unordered_map<int, int>& preOrderMap,
                                  const vector<int>& inorder, 
                                  const unordered_map<int, int>& inOrderMap, int i1, int j1) {
            
            
            if (i1 > j1) return nullptr;
            
            //minPre should be the first index in preorder where a value of inorder from i1->j1 appears
            //minIN should be the index of the inorder number that first appears in preorder
            int minPre = INT_MAX;
            int minIn;
            int corresp;
            for (int i = i1; i <= j1; i++) {
                corresp = preOrderMap.at( inorder.at(i) );
                if (corresp < minPre) {
                    minPre = corresp;
                    minIn = i;
                }
            }
            
            TreeNode* root = new TreeNode( preorder.at(minPre) );
            
            root->left = recursiveHelper(preorder, preOrderMap, inorder, inOrderMap, i1, minIn - 1);
            root->right = recursiveHelper(preorder, preOrderMap, inorder, inOrderMap, minIn + 1, j1);
            
            return root;
        }
};

for 循环让我觉得它是 O(n)，但该算法比其他 O(n) 算法花费更多的时间（以毫秒为单位）。

Answer 1

给定的代码中不仅有for循环，还有递归，这可能会使您的代码复杂度为O(n * log n)。如果您想严格证明算法的复杂性，Master theorem 会有所帮助。