Построение алгоритма дерева решений

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 листов.