Python 3 recursive O(n) solution, beats 82%
A lot of the Python solutions use slices to split the array; however, it takes O(n) to slice, making the entire algorithm O(n logn). Therefore, we create a help
A lot of the Python solutions use slices to split the array; however, it takes O(n) to slice, making the entire algorithm O(n logn). Therefore, we create a helper function to pass in the bounds of the array instead, making it O(n):\n```\ndef sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n\treturn self.helper(nums, 0, len(nums))\n\ndef helper(self, nums, lower, upper):\n\tif lower == upper:\n\t\treturn None\n\n\tmid = (lower + upper) // 2\n\tnode = TreeNode(nums[mid])\n\tnode.left = self.helper(nums, lower, mid)\n\tnode.right = self.helper(nums, mid+1, upper)\n\n\treturn node\n```\n\nPlease note the `if lower == upper: return None` statement -- since we are passing in bounds, `nums` will never be `None`. Therefore, we check if the lower and upper bounds are the same for our base case.
[]