108 Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

solution

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums) // 2
        root = TreeNode(val=nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

时间复杂度：O() 空间复杂度：O()

follow up

*426. Convert Binary Search Tree to Sorted Doubly Linked List

# 中序，记录前一个pre, 以及根节点first

class Solution:
    def __init__(self):
        self.first = None
        self.pre = None

    def treeToDoublyList(self, root):
        self.dfs(root)

        self.first.left = self.pre  # 循环链表, dfs后最后一位正是self.pre
        self.pre.right = self.first
        return self.first

    def dfs(self, root):
        if not root:
            return

        self.dfs(root.left)

        if not self.first:  # 记录首位
            self.first = root

        if self.pre: # 遍历过程中，一直记录前一位. 每一轮进行指针更新
            root.left = self.pre
            self.pre.right = root
        self.pre = root

        self.dfs(root.right)

时间复杂度：O(n) 空间复杂度：O(log(n))