1382. Balance a Binary Search Tree

https://leetcode.com/problems/balance-a-binary-search-tree

Python

In-order and rebuild

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        def inorder(node, result):
            if not node:
                return

            inorder(node.left, result)
            result.append(node.val)
            inorder(node.right, result)

        nums = []
        inorder(root, nums)

        def build(left, right):
            if left > right:
                return

            mid = (left+right) >> 1
            return TreeNode(nums[mid], build(left,mid-1), build(mid+1,right))

        return build(0, len(nums)-1)