2023.07.23 Today's Challenge

fabichoi 2023. 7. 23. 23:45

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

All Possible Full Binary Trees - LeetCode

Can you solve this real interview question? All Possible Full Binary Trees - Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0. Each element of the answer is the r

leetcode.com

트리에 대한 문제

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if not n % 2:
            return []
        if n == 1:
            return [TreeNode()]
        
        res = []
        for i in range(1, n, 2):
            left, right = self.allPossibleFBT(i), self.allPossibleFBT(n-i-1)
            
            for l in left:
                for r in right:
                    root = TreeNode(0, l, r)
                    res.append(root)
        
        return res