Unique Binary Search Trees II

정수 n이 주어질 때 1~n까지의 수로 이진 트리를 구성할 경우의 수를 얻는다. 역시 동적 프로그래밍 기법으로 같은 해를 반복하지 않도록 해야 한다

 

https://leetcode.com/problems/unique-binary-search-trees-ii/

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# Definition for a binary tree node.
class TreeNode:
    def __init__( self, x ):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def generateTrees( self, n: int, caches = None ):
        if not n:
            return [ ]

        elements = set( range( 1, n + 1 ) )
        caches = { }

        return self.__generateTrees( elements, caches )


    def __generateTrees( self, elements, caches ):
        if not elements:
            return [ ]

        # 값들을 키로 삼는다. 이로써 같은 경우를 반복하지 않는다
        key = tuple( elements )
        treeNodes = [ ]

        if key in caches:
            return caches[ key ]

        if 1 == len( elements ):
            return [ TreeNode( tuple( elements )[ 0 ] ) ]

        for element in elements:
        	# 이진 트리의 왼편 노드는 항상 루트보다 작은 값이 오도록 한다
            leftElements = set( self.__getSmallElements( element, elements ) )

            if leftElements:
                leftTrees = self.__generateTrees( leftElements, caches )
            else:
                leftTrees = []

            # 루트와 왼편 노드의 값들을 빼고는 모두 오른 노드이다
            rightElements = elements - leftElements - { element }

            if rightElements:
                rightTrees = self.__generateTrees( rightElements, caches )
            else:
                rightTrees = []

            if leftTrees and rightTrees:
                for leftTree in leftTrees:
                    for rightTree in rightTrees:
                        headNode = TreeNode( element )
                        headNode.left = leftTree
                        headNode.right = rightTree
                        treeNodes.append( headNode )
            elif leftTrees:
                for leftTree in leftTrees:
                    headNode = TreeNode( element )
                    headNode.left = leftTree
                    treeNodes.append( headNode )
            elif rightTrees:
                for rightTree in rightTrees:
                    headNode = TreeNode( element )
                    headNode.right = rightTree
                    treeNodes.append( headNode )
            else:
                assert False

        caches[ key ] = treeNodes

        return treeNodes


    def __getSmallElements( self, key, values ):
        '''주어진 값에서 키보다 작은 값들을 돌려준다
        '''
        for value in values:
            if key > value:
                yield value