894. 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 root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

範例

Example 1:

Input: n = 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

Example 2:

Input: n = 3
Output: [[0,0,0]]

Constraints:

• 1 <= n <= 20

解答

Python

class Solution:
    @cache
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n == 1:
            return [TreeNode()]
        ans = []
        for i in range(1, n-1, 2):
            ls = self.allPossibleFBT(i)
            rs = self.allPossibleFBT(n - i - 1)
            for l in ls:
                for r in rs:
                    ans.append(TreeNode(0, l, r))
        return ans

Yen-Chi ChenSun, Jul 23, 2023

C++

class Solution {
public:
    vector<TreeNode*> cache[20 + 1];

    vector<TreeNode*> allPossibleFBT(int n) {
        vector<TreeNode*> ans;
        if (n == 1) {
            ans.push_back(new TreeNode(0));
        }
        if (cache[n].size() != 0) {
            return cache[n];
        }
        for (int i = 0; i < n; i ++) {
            for (TreeNode* left : allPossibleFBT(i)) {
                for (TreeNode* right : allPossibleFBT(n - i - 1)) {
                    ans.push_back(new TreeNode(0, left, right));
                }
            }
        }
        cache[n] = ans;

        return ans;
    }
};

Jerry Wu23 July, 2023

Reference

回到題目列表