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)