894.所有可能的满二叉树

用时: 抄答案才做出来

思路很容易看出来是利用递归,但是coding才是真正的问题。

我们需要返回的是根节点,但是递归是从下至上的

尝试用动态规划解决,dp(n) 是 dp(x) 与 dp (n - x - 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
var allPossibleFBT = function(n) { 
var dp = []
var buld = function (n) {
for(let i = 1 ; i <= n ; i ++ ) {
if (i === 1) {
dp[i] = new TreeNode(0)
} else if (i % 2 === 0) {
dp[i] = undefined
} else {
dp[i] = []
for(let left = 1; left < i; left ++) {
var leftNodes = dp[left]
var rightNodes = dp[i - left - 1]
for(let j = 0 ; j < leftNodes.length ; j ++) {
for(let k = 0 ; k < rightNodes.length ; k ++) {
var node = new TreeNode(0)
node.left = leftNodes[j]
node.right = rightNodes[k]
dp[i].push(node)
}
}
}
}
}
}
buld(n)
return dp[n]
};