当前位置：首页 > news >正文

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

news 来源：原创 2024/5/17 0:42:41

2024.4.2

- - 题目来源
  - 我的题解
  - - 方法一分治
    - 方法二动态规划

题目来源

力扣每日一题；题序：894

我的题解

方法一分治

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

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