894.所有可能的满二叉树

发表于 | 分类于
思路有，但是coding 跟不上

用时： 抄答案才做出来

思路很容易看出来是利用递归，但是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]
};