LeetCode-1382平衡二进制搜索树

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        # 中序遍历得到有序数组
        def inorder(node):
            if not node:
                return []
            return inorder(node.left) + [node.val] + inorder(node.right)
        
        # 根据有序数组构建平衡二叉搜索树
        def buildBST(arr, start, end):
            if start > end:
                return None
            mid = (start + end) // 2
            node = TreeNode(arr[mid])
            node.left = buildBST(arr, start, mid - 1)
            node.right = buildBST(arr, mid + 1, end)
            return node
        
        # 获取有序数组
        vals = inorder(root)
        # 构建平衡二叉搜索树
        return buildBST(vals, 0, len(vals) - 1)