现在的位置: 首页 > 综合 > 正文

N结点二叉树中M个结点的连通子图个数 N结点二叉树中M个结点的连通子图个数

2017年11月02日 ⁄ 综合 ⁄ 共 283字 ⁄ 字号 评论关闭
 

N结点二叉树中M个结点的连通子图个数

 235人阅读 评论(0) 收藏 举报
给定一棵有N个结点的二叉树。求它的所有结点数为M的连通子图数目。 

设以n为根的结点数为m的连通子图数目 dp[n][m] 

dp[n][m] = 

dp[2n][m-1] //左孩子 

+dp[2n+1][m-1] //右孩子 

+SUM { dp[2n][i] * dp[2n+1][m-1-i]} //1<=i<m-1 左边有i个结点,右边有m-1-i个 

input: 
one tree 

output: 
SUM (dp[i][m]) //i=1...n

 
 

抱歉!评论已关闭.