Leetcode 894. All Possible Full Binary Trees(递归)


题目来源:https://leetcode.com/problems/maximum-frequency-stack/description/

标记难度:Medium

提交次数:1/1

代码效率:77.64%

题意

返回所有结点总数为N的完全二叉树。

分析

这是周赛(99)的第三题。比赛的时候我大概花了一个小时在这道题上,但是并没有做出来。我企图用一遍DFS完成所有的枚举任务,但事实上,如果不明确给定左子树和右子树的结点数目,是无法正常进行枚举的。直到最后我也没想出来怎么正常地枚举,于是我就挂了。


事实上这道题有非常明显的子问题结构,但我比赛的时候对这一点毫无知觉。显然,对于完全二叉树的每一个结点,要么它是一个叶结点,要么它的左右子树都是完全二叉树。而且显然完全二叉树的结点数目必然是奇数。于是我们可以通过递归解决这个问题:对于要求的结点总数N,枚举所有可能的左子树结点数(i,奇数)以及对应的右子树结点数(N - i - 1),然后把生成的子树拼在一起,得到所有可能的拼法。可以将N对应的所有树存起来,减少迭代的次数。

以及,令$N = 2k + 1$,则$N$个结点的不同构满二叉树的总数为卡特兰数$C_k = \frac{1}{k+1} \binom{2k}{k}$。从上述迭代公式应该是可以用数学归纳法证明的。[1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
unordered_map<int, vector<TreeNode*>> cache;

void generate(int n) {
if (n <= 0 || n % 2 == 0)
return;
if (cache.find(n) != cache.end())
return;
if (n == 1) {
TreeNode* root = new TreeNode(0);
cache[1].push_back(root);
return;
}
for (int leftNum = 1; leftNum <= n - 1; leftNum += 2) {
generate(leftNum);
generate(n - 1 - leftNum);
for (TreeNode* ltree: cache[leftNum])
for (TreeNode* rtree: cache[n - 1 - leftNum]) {
TreeNode* root = new TreeNode(0);
root->left = copy(ltree);
root->right = copy(rtree);
cache[n].push_back(root);
}
}
}

TreeNode* copy(TreeNode* root) {
if (root == NULL)
return NULL;
TreeNode* newRoot = new TreeNode(0);
newRoot->left = copy(root->left);
newRoot->right = copy(root->right);
return newRoot;
}

public:
vector<TreeNode*> allPossibleFBT(int N) {
generate(N);
return cache[N];
}
};

  1. Leetcode 894 Solution


 评论