【LeetCode】894. 所有可能的真二叉树

文章目录

- [894. 所有可能的真二叉树](https://leetcode.cn/problems/all-possible-full-binary-trees/)
- - - - 思路一：分治
      - 代码：
      - 思路二：记忆化搜索
      - 代码：

894. 所有可能的真二叉树

思路一：分治

1.递归，n==1 时，创建节点，直接返回

2.一个根有两个结点，所以结点数一定为奇数。如果为偶数，则不能构成该树，直接返回

3.所以结点总数n一定是奇数。左节点数+右结点数 = n-1(1为根节点)

4.当左树结点为i时，右树结点为n-1-i

5.推测出左右树结点分布如下： [(1,n−2),(3,n−4),(5,n−6),⋯,(n−2,1)]，遍历的步长为2

6.递归左右树，合并得到的信息

代码：

    //分治public List<TreeNode> allPossibleFBT(int n) {return dfs(n);}private List<TreeNode> dfs(int n) {List<TreeNode> res = new ArrayList<>();if (n == 1) {res.add(new TreeNode(0));//n==1 时，创建节点，直接返回return res;}if (n % 2 == 0) {//一个根有两个结点，所以结点数一定为奇数//如果为偶数，则不能构成该树，直接返回return res;}for (int i = 1; i < n; i += 2) {//结点总数n一定是奇数//左节点数+右结点数 = n-1(1为根节点)//当左树结点为i时，右树结点为n-1-i//推测出：  [(1,n−2),(3,n−4),(5,n−6),⋯,(n−2,1)]List<TreeNode> leftInfo = dfs(i);//左树的信息List<TreeNode> rightInfo = dfs(n - i - 1);//右树的信息for (TreeNode l : leftInfo) {//合并左树和右树的信息for (TreeNode r : rightInfo) {TreeNode node = new TreeNode(0, l, r);res.add(node);}}}return res;}

思路二：记忆化搜索

1.n==1 时，创建节点，直接返回

2.n>1,枚举左子树的结点数量i,右子树的结点数为n-i-1;

3.递归构造左右子树符合真二叉树的所有情况，进行合并

4.记忆化搜索，当不为空时，说明已经计算，直接拿来用。避免重复计算

代码：

    private List<TreeNode>[] f;public List<TreeNode> allPossibleFBT(int n) {f = new List[n + 1];return dfs1(n);}private List<TreeNode> dfs1(int n) {if (f[n] != null) {return f[n];}List<TreeNode> ans = new ArrayList<>();if (n == 1) {ans.add(new TreeNode(0));return f[n] = ans;}for (int i = 0; i < n - 1; i++) {int j = n - 1 - i;for (TreeNode left : dfs1(i)) {for (TreeNode right : dfs1(j)) {ans.add(new TreeNode(0, left, right));}}}return f[n] = ans;}