Leetcode 1285 Solution

This article provides solution to leetcode question 1285 (balance-a-binary-search-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 1285" in your browser address bar if you have bunnylol configured.

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

Solution

# 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:
        nodes = []



        def find(node):
            nonlocal nodes



            if not node:
                return



            find(node.left)
            nodes.append(node)
            find(node.right)



        def construct(i, j):
            nonlocal nodes



            if i > j:
                return None



            m = (i + j) // 2
            node = nodes[m]
            node.left = construct(i, m - 1)
            node.right = construct(m + 1, j)



            return node



        find(root)
        return construct(0, len(nodes) - 1)