今天考研的同學(xué)讓我?guī)退匆坏罃?shù)據(jù)結(jié)構(gòu)問題，題目是這樣的：
由23、12、45、36構(gòu)成的二叉排序樹有幾個(gè)（） ，其中AVL樹又有幾個(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 開頭的AVL樹不可能存在，因此只要枚舉23 和 36 開頭的情況，排除相同的樹即可。枚舉完發(fā)現(xiàn)分別有2個(gè)AVL樹，因此第二個(gè)空為4。
但是仔細(xì)想想，二叉樹是可以反轉(zhuǎn)的。也就是說，其實(shí)12 開頭（最小值）的樹，將樹的左右子樹交換一下，她的結(jié)構(gòu)就和45開頭（最大值）的樹一模一樣！對于23 和 36 開頭的樹也是如此（因?yàn)閷τ?3來說，有1個(gè)數(shù)比他小，2個(gè)數(shù)比他大；對于36來說，有1個(gè)樹比它大，有2個(gè)數(shù)比他小。對于樹的結(jié)構(gòu)來說，就會(huì)是左右子樹交換的問題了）！因此對于一個(gè)偶數(shù)序列，答案必定兩個(gè)空都為偶數(shù)！
因此只要給出2k位（哪怕有1000000個(gè)數(shù)）的偶數(shù)序列，只要他出答案方式不變，則不用不用不用任何計(jì)算、畫圖、枚舉?。?！直接選兩個(gè)數(shù)都為偶數(shù)的答案?。。。?/strong> 就算出答案方式改變，那也可以少計(jì)算一半?。。。。。?！
若給出2k+1奇數(shù)序列，則只需計(jì)算最中間那個(gè)樹的方案即可。
這題最難的還可以這么出：
給你 2k+1 個(gè)數(shù)，構(gòu)成的二叉排序樹有___個(gè) ，其中AVL樹又有 ___個(gè)？
來，大家一起來填空！有了上面的思路，我相信再遞歸遞歸，找找規(guī)律這題就有解了。只要有高中扎實(shí)的數(shù)學(xué)功底，以及對二叉樹本質(zhì)的了解，這題一定能作對！
