LC 105 Time complexity

LC 105. Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode.com/problems/co ... -inorder-traversal/


下面解法不是最优，但是我直觉想出来的一个解法 想请问一下这个写法的time complexity该怎麽分析？
worst case: dfs的层数总共会有 n 层但是每一层都在找 index(v) 并且做 slicing, 所以这个time complexity为 n ^ n ?

1. class Solution(object):
   
2.     def buildTree(self, preorder, inorder):
   
3.         """
   
4.         :type preorder: List[int]
   
5.         :type inorder: List[int]
   
6.         :rtype: TreeNode
   
7.         """
   
8.         que = collections.deque(preorder)
   
9.         
   
10.         return self.dfs(que, inorder)
    
11.    
    
12.     def dfs(self, que, inorder):
    
13.         if len(inorder) == 0:
    
14.             return
    
15.         if len(que) == 0:
    
16.             return
    
17.         
    
18.         v = que.popleft()
    
19.         node = TreeNode(v)
    
20.         i = inorder.index(v)
    
21. 
    
22.         node.left = self.dfs(que, inorder[:i])
    
23.         node.right = self.dfs(que, inorder[i+1:])
    
24.         
    
25.         return node

复制代码

I got answer, 最坏复杂度是O(N^2), 每次扫一遍找到root，然后剩余的n-1又属于一颗子树，所以最坏复杂度是n + n-1 + n-2 + ... + 2是N^2级别的。
Thanks you all

发成了高频题没关系。合并。