数字がリーフノードの何回表示されますか？

Question

n要素の配列があるとします。 A = {1,2,3,4,5} 合計が5です！バイナリ検索ツリーは可能です（必ずしも明確ではありません）。私の質問は、ツリー1が葉ノードとして何個登場したか、葉ノードとして何個登場したかなどです。

私が試みているもの：私はAのために見た

= {1,2,3}

2 6/3 = 2倍

1 2 + 1 = 3に表示され表示され時間

3は、2 + 1 = 3回

私はそれを一般化し、Aは= {1,2,3,4}

012場合 、それを言うことができる表示され

2 = 4分の24 = 6回

3 = 4分の24 = 6回

1 = 6 + 1 = 7回

4 = 6 + 1 = 7回

Answer 1

私たちは一般化することができますが、そのようにはできません。

アレイを並べ替えて、すべての可能なBSTを生成できます。地図/辞書のデータ構造に答えを返すブルートフォースアプローチはそれほど難しいものではありません。置換された配列の1つを与え、すべての葉を見つける関数を書く。ルートとして最初の要素をとり、ルート以下のすべての要素を左に送り、すべての要素を右に送り、両方の要素に対してこの関数を再帰的に呼び出します。これらの値を組み合わせた後に戻ります。

最後に、すべての可能な順列の値を結合します。

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,2,3,4,5]ため

{1: 12, 2: 8, 3: 8, 4: 12} 

、それは：

{1: 60, 2: 40, 3: 40, 4: 40, 5: 60} 

パターンが見えますか？まあ、一つの最後の例。最大6のためにそれがある：あなたの最初の例では

{1: 360, 2: 240, 3: 240, 4: 240, 5: 240, 6: 360}