894. 所有可能的真二叉树 - Kotlin 动态规划

Problem: 894. 所有可能的真二叉树

思路

设为i个节点能够组成的所有真二叉树，结合DP的思想，可以想到，i个节点的情况可以理解为1个根节点连接个子节点的情况，由于左子树和右子树的节点和为，可以枚举左子树节点的情况，则右子树节点即为

对于我们枚举得到的left，遍历left个节点情况下能组成的所有二叉树，令根节点的左节点连接该二叉树，即为根节点左子树的所有情况。右子树同理，在遍历到所有情况后，将其加入当前情况下的列表。

这种做法求的是所有二叉树的情况，考虑真二叉树：我们要考虑的实际上只有根节点，因为子问题求得的结果已经是满足条件的真二叉树。由题可知，当根节点树为真二叉树时，要么左节点和右节点均为空（除n=1外均不可能），要么左节点和右节点均不为空

因此令遍历即可，此时，满足左右节点均不为空

复杂度

时间复杂度:

空间复杂度:

Code

class Solution {
    fun TreeNode.clone():TreeNode {
        val clone=TreeNode(this.`val`)
        clone.left=this.left?.clone()
        clone.right=this.right?.clone()
        return clone
    }

    fun allPossibleFBT(n: Int): List<TreeNode?> {
        val dp = Array<MutableList<TreeNode?>>(n+1){ArrayList()}
        
        dp[1].add(TreeNode(0))
        
        for(i in 2..n){
            for(left in 1 until i-1){
                val right=i-1-left
                for(leftNode in dp[left]){
                    for(rightNode in dp[right]){
                        val root=TreeNode(0)
                        root.left=leftNode?.clone()
                        root.right=rightNode?.clone()
                        dp[i].add(root)
                    }
                }
            }
        }

        return dp[n]
    }
}