O(n) Python recursive solution


#1
class Solution:
# @param A : list of integers
# @param B : list of integers
# @return the root node in the tree
def buildTree(self, A, B):
    if A:
        root = TreeNode(A[0])
        idx = B.index(A[0])
        root.left = self.buildTree(A[1:idx + 1], B[:idx + 1])
        root.right = self.buildTree(A[idx + 1:], B[idx + 1:])
        return root

#2

You are using B.index(A[0]). Thats already O(n) and you are using it in a recursion, means your solutions has a worse complexity than O(n). Please proof me wrong, if it is incorrect.

Additionaly you use slicing which is also a O(n) operation.