Вертикальная сумма двоичного дерева

Question

Как найти вертикальную сумму двоичного дерева.

Например, Рассмотрим бинарное дерево ниже,

     1 
        /\ 
       / \ 
       / \ 
       2  3 
       /\ /\ 
      / \ / \ 
       4 5 6 7 
      /\/\/\/\ 
      5 9 1 3 6 7 5 5 

Для приведенного выше дерева, вертикальная сумма должна быть рассчитана следующим образом,

• Строка 1: 5
• Строка 2: 4
• Строка 3: 2,9,1
• Строка 4: 5
• Строка 5: 1,3,6
• Строка 6: 6
• Строка 7: 3,7,5
• Строка 8: 7
• Строка 9: 5

выход должен быть:

5,4,12,5,10,6,15,7,5 

Answer 1

Сначала вы должны найти позиции, вы можете сделать это путем подсчета числа левых и права тратить на конкретный узел:

    1  : l = 0, r = 0 
       /\ 
      / \ 
     l=1,r=0 2  3 : l = 0, r = 1. 
      /\ /\ 
    ... 4...5 6...7 .... 

Просто вы можете пройти ваш бинарное дерево и, наконец, вычислить LorR = NumberOfLeft - NumberOfRights для каждого узла, то группа эти цифры (по их стоимости LorR) вместе и найти каждую сумму групп (распечатать их из самых положительных до самых отрицательного значения LorR) ,

Обновление: Это не отвечает за дерево с высотой более двух, мы можем исправить эту проблему с небольшими изменениями в алгоритме.

Мы можем видеть дерево, как пирамиды, каждая вершина пирамиды имеет длину 1, после того, как каждая ветвь оставшаяся часть ветви равно, что прошло в последнем движении, мы покажем это на картинке для дерева высоты 3:

    1 
       /\ 
      / \ 
      / \ 
      2  3 upto this we used 1/2 size of pyramid 
      /\ /\ 
     / \ / \ 
      4 5 6 7 upto this we used 1/2 + 1/4 part of pyramid 
     /\/\/\/\ 
     5 9 1 3 6 7 5 5 upto this we used 1/2 + 1/4 + 1/4 part of pyramid 

Это означает, что на каждом шаге мы вычисляем левые значения по их высоте (фактически каждый раз умножая 1/2 будет добавлен к левому значению, за исключением последнего времени, равного h-1-й значению).

Итак, для этого случая мы имеем: 1 в корне в группе 0, 3 в листе в группе -1/2 + 1/4 + 1/4 = 0, 6 в листе находится в группе 1/2 - 1/4 - 1/4 = 0

1 в листе находится в -1/2 + 1/4 - 1/4 = -1/2 и так далее.

Для предотвращения округления 1/(2^x) до нуля или других проблем мы можем умножить наши коэффициенты (1/2, 1/4, 1/8, ...) на 2 ^h-1 , Фактически в первом случае я написал, что коэффициенты умножаются на 2 ^2-1.

Answer 2

метод грубой силы в псевдокоде:

columnAdd(tree): 
    sumPerColumn = new Map<int,int>(); 
    traverse(tree.root, sumPerColumn, 0); 
    return sumPerColumn; 

traverse(node, sumPerColumn, currentColumn): 
    sumPerColumn[currentColumn] ++; 
    traverse(node.left, sumPerColumn, currentColumn-1); 
    traverse(node.right, sumPerColumn, currentColumn+1); 

это даст:

{-2: 4, 
    -1: 2, 
    0: 12, 
    1: 3, 
    2: 7} 

Answer 3

Насколько я понял, двигаясь влево -1, перемещение вправо +1 , Вы можете использовать модифицированные dfs. Здесь предполагается, что add(col, value) определено

dfs(col, node) 
begin 
    add(col, node.value) 
    if(haveLeft) 
    dfs(col-1, left) 
    if(haveRight) 
    dfs(col+1, right) 
end 

Предполагая, что добавить работы в O (1) (используя HashMap или простой массив, например), это работает в O (N).