分治dp，LeetCode 894. 所有可能的真二叉树

本文主要是介绍分治dp，LeetCode 894. 所有可能的真二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、题目

1、题目描述

2、接口描述

​cpp

python3

3、原题链接

二、解题报告

1、思路分析

F1 回溯

F2 动态规划

2、复杂度

3、代码详解

​分治

cpp

python3

dp

cpp

python3

---

一、题目

1、题目描述

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

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

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

2、接口描述

​cpp

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<TreeNode*> allPossibleFBT(int n) {}
};

python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:

3、原题链接

894. 所有可能的真二叉树

---

二、解题报告

1、思路分析

F1 回溯

首先对于偶数个节点的情况直接返回空即可

然后分析，对于n（n为奇数）个节点的二叉树，根节点占一个节点，那么其左右节点的情况为

<1, n - 2>, <3, n - 4>……

所以我们发现构造n个节点的真二叉树可以分治为构造两个子真二叉树的问题

所以我们枚举左右儿子的节点数目进行分治构造即可

F2 动态规划

我们可以换种思路，自底向上分析

对于n个节点的真二叉树可以分为根节点加上两个子真二叉树

同样的，我们也可以由两个子真二叉树构造出一棵真二叉树

我们设f[k]（k >= 1）为n = 2 * k - 1个节点的真二叉树的所有可能序列

那么f[i] = node(f[k], f[i - k])，这个递推还是比较简单的

相较于分治的做法，时间复杂度并未降低，但是省去了递归开销 

由于数据量只到20，因此我们可以预处理出f[1]~f[10]

2、复杂度

分治：时间复杂度： 空间复杂度：

dp：预处理时间复杂度预处理空间复杂度：，N = 11

查询的时间复杂度和空间复杂度都是O(1)

3、代码详解

​分治

cpp

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<TreeNode*> allPossibleFBT(int n) {vector<TreeNode*> ret;if(n % 2 == 0) return ret;if(n == 1) return {new TreeNode(0)};for(int i = 1; i < n; i += 2){vector<TreeNode*> leftnodes(allPossibleFBT(i)), rightnodes(allPossibleFBT(n - i - 1));for(TreeNode* x : leftnodes)for(TreeNode* y : rightnodes)ret.emplace_back(new TreeNode(0, x, y));}return ret;}
};

python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:if n % 2 == 0:return []if n == 1:return [TreeNode()]ret = []for i in range(1, n, 2):leftnodes, rightnodes = self.allPossibleFBT(i), self.allPossibleFBT(n - i - 1)ret.extend([TreeNode(0, x, y) for x in leftnodes for y in rightnodes])return ret

python也可以记忆化搜索，得到和dp相媲美的效率

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:@cachedef allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:if n % 2 == 0:return []if n == 1:return [TreeNode()]ret = []for i in range(1, n, 2):leftnodes, rightnodes = self.allPossibleFBT(i), self.allPossibleFBT(n - i - 1)ret.extend([TreeNode(0, x, y) for x in leftnodes for y in rightnodes])return ret

dp

cpp

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
vector<TreeNode*> f[11];
bool init = []{f[1] = { new TreeNode() };for(int i = 2; i < 11; i++)for(int j = 1; j < i; j++)for(TreeNode* x : f[j])for(TreeNode* y : f[i - j])f[i].emplace_back(new TreeNode(0, x, y));return false;
}();
class Solution {
public:vector<TreeNode*> allPossibleFBT(int n) {return f[n & 1 ? (n + 1) / 2 : 0];}
};

python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
f = [[] for _ in range(11)]
f[1] = [TreeNode()]
for i in range(2, 11):f[i] = [TreeNode(0, x, y) for j in range(1, i)for x in f[j]for y in f[i - j]]
class Solution:def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:return f[(n + 1) // 2] if n & 1 else []

这篇关于分治dp，LeetCode 894. 所有可能的真二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---