構建一個算法決策樹

Question

有人問我今天晚上做的這個問題，在接受採訪時：

構建決策樹的任何三個輸入到這個算法：

For i = 1 to n - 1 do 
    If L[i] > L[i+1] 
     swap(L[i],L[i+1]) 
For i = n-1 downto 2 do 
    If L[i] < L[i-1] 
     swap(L[i],L[i-1]) 

我相信我的解決方案是不正確，因爲我出來了16葉。我做了以下內容：

        Root : 
            {a, b, c} 
            / \ 
         (i>i+1) / \ (i<i+1) 
           /  \ 
           {b,a,c}  {a,b,c} 
          / \  / \ 
          / \  / \ 
          /  \ /  \ 
         {b,c,a} {b,a,c} {a,c,b} {a,b,c} 

這完成了第一圈，我則擴大了輸入以同樣的方式，第二循環中，在每個節點假設一個決定去<和一個去>，導致每次兩個答案來自每個節點，並最終給你16葉。

這個錯誤？如果不是，應該怎麼做？

Answer 1

對於n = 3，第二個循環只運行一次，對於i = 2。所以每個節點有兩個答案，你會得到2 * 4 = 8葉。