894. All Possible Full Binary Trees

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

Python

class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if not n % 2:
            return []

        def backtrack(i):
            if i == 1:
                return [TreeNode(val=0)]
            tree = []
            for j in range(1, i-1):
                for left in backtrack(j):
                    for right in backtrack(i-j-1):
                        tree.append(
                            TreeNode(0, left, right)
                        )
            return tree

        return dfs(n)