Medium

题目描述

给定一个整数 n，返回所有具有 n 个节点的可能的满二叉树列表。答案中每棵树的每个节点都必须具有 Node.val == 0。

答案的每个元素都是一个可能的树的根节点。你可以按任何顺序返回最终的树列表。

满二叉树是每个节点恰好有 0 个或 2 个子节点的二叉树。

示例 1：

输入：n = 7
输出：[[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]]

示例 2：

输入：n = 3
输出：[[0,0,0]]

约束条件：

  • 1 <= n <= 20

解题思路

这是一道关于树的递归构造问题。我们需要理解满二叉树的性质：每个节点要么是叶子节点（0个子节点），要么有恰好2个子节点。

关键观察：

  1. 如果 n 是偶数，则无法构造满二叉树。因为满二叉树的节点数必须是奇数（根节点 + 左子树节点数 + 右子树节点数，其中左右子树的节点数都是奇数）
  2. 对于奇数 n，我们可以枚举左子树的节点数 i（1, 3, 5, …），那么右子树的节点数就是 n-1-i

递归思路：

  • 递归构造所有可能的左子树和右子树
  • 将每种左子树与每种右子树组合，构成新的满二叉树
  • 使用记忆化避免重复计算

算法步骤：

  1. 如果 n 为偶数，直接返回空列表
  2. 如果 n = 1，返回只有一个根节点的树
  3. 对于 n > 1，枚举左子树节点数，递归构造左右子树，然后组合所有可能性

这个解法使用动态规划和记忆化，能够有效避免重复子问题的计算。

代码实现

class Solution {
private:
    unordered_map<int, vector<TreeNode*>> memo;
    
public:
    vector<TreeNode*> allPossibleFBT(int n) {
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        
        vector<TreeNode*> result;
        
        if (n % 2 == 0) {
            memo[n] = result;
            return result;
        }
        
        if (n == 1) {
            result.push_back(new TreeNode(0));
            memo[n] = result;
            return result;
        }
        
        for (int i = 1; i < n; i += 2) {
            vector<TreeNode*> leftTrees = allPossibleFBT(i);
            vector<TreeNode*> rightTrees = allPossibleFBT(n - 1 - i);
            
            for (TreeNode* left : leftTrees) {
                for (TreeNode* right : rightTrees) {
                    TreeNode* root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    result.push_back(root);
                }
            }
        }
        
        memo[n] = result;
        return result;
    }
};

class Solution:
    def __init__(self):
        self.memo = {}
    
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n in self.memo:
            return self.memo[n]
        
        if n % 2 == 0:
            self.memo[n] = []
            return []
        
        if n == 1:
            self.memo[n] = [TreeNode(0)]
            return [TreeNode(0)]
        
        result = []
        for i in range(1, n, 2):
            left_trees = self.allPossibleFBT(i)
            right_trees = self.allPossibleFBT(n - 1 - i)
            
            for left in left_trees:
                for right in right_trees:
                    root = TreeNode(0)
                    root.left = left
                    root.right = right
                    result.append(root)
        
        self.memo[n] = result
        return result

public class Solution {
    private Dictionary<int, IList<TreeNode>> memo = new Dictionary<int, IList<TreeNode>>();
    
    public IList<TreeNode> AllPossibleFBT(int n) {
        if (memo.ContainsKey(n)) {
            return memo[n];
        }
        
        List<TreeNode> result = new List<TreeNode>();
        
        if (n % 2 == 0) {
            memo[n] = result;
            return result;
        }
        
        if (n == 1) {
            result.Add(new TreeNode(0));
            memo[n] = result;
            return result;
        }
        
        for (int i = 1; i < n; i += 2) {
            IList<TreeNode> leftTrees = AllPossibleFBT(i);
            IList<TreeNode> rightTrees = AllPossibleFBT(n - 1 - i);
            
            foreach (TreeNode left in leftTrees) {
                foreach (TreeNode right in rightTrees) {
                    TreeNode root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.Add(root);
                }
            }
        }
        
        memo[n] = result;
        return result;
    }
}

var allPossibleFBT = function(n) {
    if (n % 2 === 0) return [];
    
    const memo = new Map();
    
    function helper(nodes) {
        if (memo.has(nodes)) return memo.get(nodes);
        
        if (nodes === 1) {
            memo.set(1, [new TreeNode(0)]);
            return memo.get(1);
        }
        
        const result = [];
        for (let i = 1; i < nodes; i += 2) {
            const leftTrees = helper(i);
            const rightTrees = helper(nodes - 1 - i);
            
            for (const left of leftTrees) {
                for (const right of rightTrees) {
                    const root = new TreeNode(0);
                    root.left = left;
                    root.right = right;
                    result.push(root);
                }
            }
        }
        
        memo.set(nodes, result);
        return result;
    }
    
    return helper(n);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^n) - 满二叉树的数量呈指数增长，需要构造所有可能的树
空间复杂度O(2^n) - 需要存储所有可能的树结构，递归栈深度为 O(n)