一个高度为N且只有N个不同颜色的节点的二叉树有多少种形状（颜

[问答题]

一个高度为N且只有N个不同颜色的节点的二叉树有多少种形状（颜色不同算不同）？用^表示次方！表示阶乘。

心涛骇浪

2^(n-1)*n!

发表于 2020-08-01 09:36:44 回复(0)

牛客7760634号

设不算颜色不同有 x 种结构：

x 的解法

N个节点是取一个节点为根节点另外取0-N-1个节点为左节点构成的

N个节点构成的数目就是左节点的可构成个数*右节点的个数可构成的个数

那么，算上不同颜色应该有 N!*x 种形状

def numOfTreeStructure(n):
    """
    n个节点 每个节点不同颜色 则一共有多少种结构
    :param n:
    :return:
    """
    def num_structure_without_color(n):
        """
        不考虑颜色一共有多少种结构
        """
        if n == 0:
            return 0
        result = {0:1, 1: 1}
        for i in range(2,n+1):
            tmp = 0
            for j in range(i):
                tmp += result[j]*result[i-1-j]
            result[i] = tmp
        return result[n]
    return math.factorial(n) * num_structure_without_color(n)

发表于 2019-08-22 11:57:15 回复(0)