[99클럽] 17일차 TIL

https://leetcode.com/problems/all-possible-full-binary-trees/submissions/1279496386/

 

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        dp = {}
        dp[1] = [TreeNode(0)]
        def dfs(cnt):
            ans = []
            if cnt in dp:
                return dp[cnt]
            for i in range(1, cnt, 2):
                left_trees = dfs(i)
                right_trees = dfs(cnt - i - 1)

                for left in left_trees:
                    for right in right_trees:
                        root = TreeNode(0)
                        root.left = left
                        root.right = right
                        ans.append(root)
            dp[cnt] = ans
            return ans

        return dfs(n)

 

 

리트코드의 문제를 풀어보았습니다.

 

역시나 아직도 어색한 부분이 많지만 그래도 익숙해지려고 노력하고 있습니다