# 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:
        #TC: O(len(root))
        #SC: O(len(root))
        #First use inorder trasversal to concert original tree to list
        #Then contruct the tree
        List = []

        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            List.append(root.val)
            dfs(root.right)

        dfs(root)

        n = len(List)
        dfs(root)
        rootidx = List[n//2]

        def ConstructTree(lower, upper):

            if lower > upper:
                return

            rootidx = (lower + upper) // 2 
            Node = TreeNode(List[rootidx])

            Node.left = ConstructTree(lower, rootidx-1)
            Node.right = ConstructTree(rootidx+1, upper)

            return Node

        return ConstructTree(0, n-1)