2024.4.2力扣每日一题——所有可能的真二叉树

题目来源

力扣每日一题；题序：894

我的题解

方法一 分治

• 只有一个节点必然是真二叉树
• 偶数个节点的树必然不是真二叉树，因为每个节点恰好有0或者2个子节点（详细证明可以使用归纳法，见官方题解）
• 当节点数大于1并且为奇数时，可以分别枚举左子树和右子树的根节点数，然后递归构造左子树和右子树。

时间复杂度：$O(\frac{2^n}{\sqrt{n}})$，其中 n 是给定的真二叉树的结点数。只有当 n 是奇数时才存在真二叉树，记 2k+1，由 n 个结点组成的真二叉树的数量是第 k 个卡特兰数$\frac{C(2k,k)}{k+1}$，其渐进上界为 $O(\frac{4^k}{k\sqrt{k}})=O(\frac{2^n}{n\sqrt{n}})$，对于每个真二叉树需要 O(n) 的时间生成和添加到答案中，因此时间复杂度是 $O(\frac{2^n}{\sqrt{n}})$。
空间复杂度：O(n)

public List<TreeNode> allPossibleFBT(int n) {
    List<TreeNode> res=new ArrayList<>();
    //偶数个节点无法得到真二叉树
    if(n%2==0)
        return res;
    return partition(n);
}
public List<TreeNode> partition(int n){
    List<TreeNode> res=new ArrayList<>();
    //只有一个节点必然是真二叉树
    if(n==1){
        res.add(new TreeNode(0));
        return res;
    }
    for(int i=1;i<n;i+=2){
        List<TreeNode> lefts=partition(i);
        List<TreeNode> rights=partition(n-i-1);
        for(TreeNode left:lefts){
            for(TreeNode right:rights){
                TreeNode root=new TreeNode(0,left,right);
                res.add(root);
            }
        }
    }
    return res;
}

方法二 动态规划

先构造节点数量为 1 的子树，然后构造节点数量为 5 的子树，然后依次累加即可构造出含有节点数目为 n 的真二叉树。

• 节点数目序列分别为 [(1,1)] 的子树可以构造出节点数目 3的子树；
• 节点数目序列分别为 [(1,3),(3,1)] 的子树可以构造出节点数目 5 的真二叉树；
• 节点数目序列分别为 [(1,5),(3,3),(5,1)] 的子树可以构造出节点数目 7 的真二叉树；
• 节点数目序列分别为 [(1,i−2),(3,i−4),⋯ ,(i−2,1)]的子树可以构造出节点数目 iii 的真二叉树；

如果构造节点数目为 nnn 真二叉树，此时可以从节点数目序列为 [(1,n−2),(3,n−5),⋯ ,(n−2,1)]的真二叉树中构成，按照所有可能的组合数进行枚举，即可构造成节点数目为 n 的真二叉树。

时间复杂度：$O(\frac{2^n}{\sqrt{n}})$
空间复杂度：O(1)

public List<TreeNode> allPossibleFBT(int n) {
    //偶数个节点无法得到真二叉树
    if(n%2==0)
        return new ArrayList<>();
    List<TreeNode>[] dp=new ArrayList[n+1];
    for(int i=0;i<=n;i++)
        dp[i]=new ArrayList<>();
    dp[1].add(new TreeNode(0));
    //总节点数
    for(int i=3;i<=n;i+=2){
        //左子树的根节点数
        for(int j=1;j<i;j+=2){
            for(TreeNode left:dp[j]){
                for(TreeNode right:dp[i-1-j]){
                    TreeNode root=new TreeNode(0,left,right);
                    dp[i].add(root);
                }
            }
        }
    }
    return dp[n];
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~