Solutions in recursive DFS, iterative DFS and BFS
Solutions using 3 popular tamplates: recursive DFS, iterative DFS, and BFS.\n\nSearching boundaries in these solutions are python-style: [lower, upper), left in
Solutions using 3 popular tamplates: recursive DFS, iterative DFS, and BFS.\n\n*Searching boundaries in these solutions are python-style: [lower, upper), left inclusive, right exclusive.*\n```\n\t#################\n\t# recursive dfs #\n\t#################\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        if not nums:\n            return None\n        mid = len(nums) // 2\n        root = TreeNode(nums[mid])\n        root.left = self.sortedArrayToBST(nums[:mid])\n        root.right = self.sortedArrayToBST(nums[mid+1:])\n        return root\n\t\t\n\t#################\n\t# iterative dfs #\n\t#################\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        if not nums:\n            return None\n\n        root = TreeNode()\n        # (node, lower, upper) with [lower, upper)\n        stack = [(root, 0, len(nums))]\n        \n        while stack:\n            node, lower, upper = stack.pop()\n            mid = (lower + upper) // 2\n            node.val = nums[mid]\n            node.left = TreeNode() if mid > lower else None\n            node.right = TreeNode() if upper > mid + 1 else None\n            if node.right: stack.append((node.right, mid+1, upper))\n            if node.left: stack.append((node.left, lower, mid))\n                \n        return root\n\t\t\n\t#######\n\t# bfs #\n\t#######\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        if not nums:\n            return None\n\n        root = TreeNode()\n        # (node, lower, upper) with [lower, upper)\n        q = collections.deque([(root, 0, len(nums))])\n        \n        while q:\n            size = len(q)\n            for _ in range(size):\n                node, lower, upper = q.popleft()\n                mid = (lower + upper) // 2\n                node.val = nums[mid]\n                node.left = TreeNode() if lower < mid else None\n                node.right = TreeNode() if mid + 1 < upper else None\n                if node.left: q.append((node.left, lower, mid))\n                if node.right: q.append((node.right, mid + 1, upper))\n                    \n        return root\n```
['Stack', 'Depth-First Search', 'Breadth-First Search', 'Recursion', 'Queue', 'Iterator']