LeetCode 풀기 - 1382. Balance a Binary Search Tree

1382. Balance a Binary Search Tree

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

Balance a Binary Search Tree - LeetCode

문제)

솔루션1) - Bianry Search Tree

풀이 전략:

• 넘겨 받은 root 트리를 inorder 순회하여 정렬된 val를 리스트를(nums) 구성
• Binary Search Tree 클래스 구현
• Balanced BST를 구성하기 위해서는 부모가 최대한 중간값을 갖는 것이 중요!
• nums의 중간값을 재귀적으로 찾아가면서 tree에 insert 작업

# 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):
        nums = []
        tree = BST()

        def inorder(node):
            if node is None: 
                return
            inorder(node.left)
            nums.append(node.val)
            inorder(node.right)

        def recur(nums):
            if len(nums) == 0:
                return
            
            mid = len(nums) // 2
            tree.insert(nums[mid])
            recur(nums[:mid])
            recur(nums[mid + 1:])

        inorder(root)
        recur(nums)
        return tree.root


class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if self.root is None:
            self.root = TreeNode(val)
            return
        self._insert(self.root, val)

    def _insert(self, node, val):
        if node is None:
            return TreeNode(val)

        if val < node.val:
            node.left = self._insert(node.left, val)
        else:
            node.right = self._insert(node.right, val)
        return node

솔루션2) - Binary Search Tree (코드 사이즈 감소)

솔루션1 코드의 축약 버전입니다.

# 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):
        nums = []
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            nums.append(node.val)
            inorder(node.right)
            
        def bst(nums):
            if not nums:
                return
            mid = len(nums)//2
            node = TreeNode(nums[mid])
            node.left = bst(nums[:mid])
            node.right = bst(nums[mid+1:])
            return node
            
        inorder(root)
        return bst(nums)