假设你有一个包含 n 个元素的数组 A = {1,2,3,4,5} 一共5个!二叉搜索树是可能的(不一定不同)现在我的问题是有多少树 1 出现为叶节点,有多少树 2 出现为叶节点等等?
我尝试过的:
我见过 A = {1,2,3}
2 出现 6/3 = 2 次p>
1 出现 2+1 = 3 次
3出现2+1=3次
我可以概括一下,然后说吗? 如果 A= {1,2,3,4}
2 = 24/4 = 6 次
3 = 24/4 = 6 次
1 = 6+1 = 7 次
4 = 6+1 = 7 次
最佳答案
我们可以概括,但不是那样。
您可以尝试置换数组并生成所有可能的 BST。在 map /字典数据结构中返回答案的蛮力方法不应该那么难。首先编写一个函数,给定一个置换数组,找到所有叶子。它以第一个元素为根,将小于根的所有元素发送到左侧,将所有大于根的元素发送到右侧,并为这两个元素递归调用此函数。然后它在组合这些值后返回。
最后,组合所有可能排列的值。
Python 中的一种可能方法:
from itertools import permutations
def func(arr):
if not arr: return {}
if len(arr)==1: return {arr[0]}
ans = set()
left = func([v for v in arr[1:] if v<arr[0]])
right = func([v for v in arr[1:] if v>=arr[0]])
ans.update(left)
ans.update(right)
return ans
arr = [1,2,3,4]
ans = {i:0 for i in arr}
for a in permutations(arr):
dic = func(a)
print(a,":",dic)
for k in dic:
ans[k]+=1
print(ans)
对于 [1,2,3]
它输出:
(1, 2, 3) : {3}
(1, 3, 2) : {2}
(2, 1, 3) : {1, 3}
(2, 3, 1) : {1, 3}
(3, 1, 2) : {2}
(3, 2, 1) : {1}
{1: 3, 2: 2, 3: 3}
对于 [1,2,3,4]
,只有最后一行,即答案是:
{1: 12, 2: 8, 3: 8, 4: 12}
对于[1,2,3,4,5]
,它是:
{1: 60, 2: 40, 3: 40, 4: 40, 5: 60}
你能看出规律吗?好吧,最后一个例子。对于最多 6
,它是:
{1: 360, 2: 240, 3: 240, 4: 240, 5: 240, 6: 360}
关于algorithm - 一个数字作为叶节点出现了多少次?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47249303/