今天考研的同學(xué)讓我?guī)退匆坏罃?shù)據(jù)結(jié)構(gòu)問(wèn)題住闯，題目是這樣的：
由23、12拂酣、45秋冰、36構(gòu)成的二叉排序樹(shù)有幾個(gè)（） ，其中AVL樹(shù)又有幾個(gè)（）婶熬？
A. 13, 4;
B. 13, 5;
C. 14, 5;
D. 14, 4;
答案： D
看到這題的第一反應(yīng)是剑勾，首先將序列排序?yàn)?：12埃撵、23、36虽另、45暂刘，然后用枚舉法。
當(dāng)然答案也是這么給的捂刺。
有 種情況谣拣， 枚舉的時(shí)候發(fā)現(xiàn)12 和 45 開(kāi)頭的AVL樹(shù)不可能存在，因此只要枚舉23 和 36 開(kāi)頭的情況族展，排除相同的樹(shù)即可森缠。枚舉完發(fā)現(xiàn)分別有2個(gè)AVL樹(shù)，因此第二個(gè)空為4仪缸。
但是仔細(xì)想想贵涵，二叉樹(shù)是可以反轉(zhuǎn)的。也就是說(shuō)恰画，其實(shí)12 開(kāi)頭（最小值）的樹(shù)宾茂，將樹(shù)的左右子樹(shù)交換一下，她的結(jié)構(gòu)就和45開(kāi)頭（最大值）的樹(shù)一模一樣拴还！對(duì)于23 和 36 開(kāi)頭的樹(shù)也是如此（因?yàn)閷?duì)于23來(lái)說(shuō)跨晴，有1個(gè)數(shù)比他小，2個(gè)數(shù)比他大自沧；對(duì)于36來(lái)說(shuō)坟奥，有1個(gè)樹(shù)比它大，有2個(gè)數(shù)比他小拇厢。對(duì)于樹(shù)的結(jié)構(gòu)來(lái)說(shuō)爱谁，就會(huì)是左右子樹(shù)交換的問(wèn)題了）！因此對(duì)于一個(gè)偶數(shù)序列孝偎，答案必定兩個(gè)空都為偶數(shù)访敌！
因此只要給出2k位（哪怕有1000000個(gè)數(shù)）的偶數(shù)序列，只要他出答案方式不變衣盾，則不用不用不用任何計(jì)算寺旺、畫(huà)圖、枚舉Ｊ凭觥Ｗ杷堋！直接選兩個(gè)數(shù)都為偶數(shù)的答案９础３旅А！！ 就算出答案方式改變走搁，那也可以少計(jì)算一半６栏獭！Ｋ街病＜烧ぁ！Ｇ凇索绪！
若給出2k+1奇數(shù)序列，則只需計(jì)算最中間那個(gè)樹(shù)的方案即可躯肌。
這題最難的還可以這么出：
給你 2k+1 個(gè)數(shù)者春，構(gòu)成的二叉排序樹(shù)有___個(gè) ，其中AVL樹(shù)又有 ___個(gè)清女？
來(lái)，大家一起來(lái)填空晰筛！有了上面的思路嫡丙，我相信再遞歸遞歸，找找規(guī)律這題就有解了读第。只要有高中扎實(shí)的數(shù)學(xué)功底曙博，以及對(duì)二叉樹(shù)本質(zhì)的了解，這題一定能作對(duì)怜瞒！
