LeetCode_Unique Binary Tree

1st Trial

1. 가능한 조합의 경우의 수 생성

2. 각 조합에 대해 이진트리 구성

3. 모든 이진트리 서로 비교

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        # 연결리스트 노드
        class Node:
            def __init__(self, value):
                self.value = value
                self.left  = None
                self.right = None
        # 이진트리
        class BST :
            def __init__(self,root):
                self.root = root
                
            def insert(self,value):
                self.current_node = self.root
                while True:
                    if value < self.current_node.value:
                        if self.current_node.left != None :
                            self.current_node = self.current_node.left
                        else :
                            self.current_node.left = Node(value)
                        break
                    else : 
                        # 오른쪽
                        if self.current_node.right != None:
                            self.current_node = self.current_node.right
                        else:
                            self.current_node.right = Node(value)
                        break
            
        #  순열 경우수 만들기 위한 DFS
        def DFS(L) :
            if L == n + 1:
                AllCase.append(res[1:L])
                return
            else:
                for i in range(1,n+1):
                    # 방문 안했다면
                    if ch[i] == 0 :
                        # 방문 표시
                        ch[i] = 1
                        # 순열 요소 생성
                        res[L] = i
                        # DFS 
                        DFS( L + 1) 
                        # 방문 표시 해제
                        ch[i] = 0
                        
        # 이진 트리 비교 코드
        def IsSameTree(p,q):
            # 값 먼저 비교
            if p.value == q.value :
                # 자식들도 같은지 확인하기
                # 1) 왼쪽 자식
                if not IsSameTree(p.left, q.left):
                    return False
                # 2) 오른쪽 자식
                if not IsSameTree(p.right, q.right):
                    return False
                return True
            else:
                return False
        
        # 1) 순열 경우의 수 배열 만들기
        # AllCase : 총 순열 경우의 수를 저장할 배열
        AllCase = []
        # 각 순열을 담을 배열
        res = [0] * (n+1)
        # 순열 만들때의 체크리스트
        ch = [0] * ( n + 1 )
        
        # 순열 만들기
        DFS(1)
        

        # 2) 이진트리 형성 시작
        # 모든 이진트리 경우의 수
        AllBSTs = []
        for case in AllCase :
            root = Node(case[0])
            bst  = BST(root)
            for j in range(1,len(case)):
                bst.insert(case[j])
            AllBSTs.append(bst)
            
        
        # 3) 이진트리들 간의 비교 시도
        for i in range(len(AllBSTs)-1):
            for j in range( i+1, len(AllBSTs)):
                print(IsSameTree(AllBSTs[i].root,AllBSTs[i].root))
                print("i,j", i,j)
                print("ith",AllBSTs[i].root.value)
                print("jth",AllBSTs[j].root.value)
        
        
       
                

하지만, 작성한 IsSameTree 코드에서 다음과 같은 에러가 난다

2nd Trial : Solved

동적 계획법 사용

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        # numTree[4] = numTree[0] * numTree[3] + numTree[1] * numTree[2] + numTree[2] * numTree[1] + numTree[3] * numTree[1]
        
        numTree = [1] * (n+1) 
        
        # 0 node = 1 tree
        # 1 node = 1 tree
        # 따라서, 2부터 바로 시작한다
        for nodes in range(2, n + 1):
            # nodes는 root node이다.
            total = 0
            # 여기서, 해당 nodes가 root node일때, 만들 수 있는 트리 경우의 수를 구한다
            for root in range(1, nodes + 1):
                
                # 왼쪽 Tree 에 들어갈 노드
                left = root - 1
                # 오른쪽 Tree에 들어갈 노드
                right = nodes - root
                total += numTree[left] * numTree[right]
            
            # cashing
            # numTree라는 배열에는, 1 ~ n 까지의 숫자가 루트노드일때의 만들어지는 트리 개수를 의미한다
            numTree[nodes] = total
        
        return numTree[n]