Двоичные суммы веток дерева без рекурсии

Question

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

public static List<Integer> branchSums(BinaryTree root) {
    LinkedList<BinaryTree> toVisit = new LinkedList<>();
    BinaryTree current = root;
    List<Integer> sums = new ArrayList<>();
    int sum = 0;

    while (current != null || !toVisit.isEmpty()) {
        while (current != null) {
            sum += current.value;
            toVisit.push(current);
            current = current.left;
        }

        current = toVisit.pop();

        // if found leaf add sum to results and decrement sum by current node
        if (current.left == null && current.right == null) {
            sums.add(sum);
            sum -= current.value;
        }

        current = current.right;
    }

return sums;
}

Пример ввода:

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

Пример вывода [15, 16, 18, 10, 11]

Answer 1

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

Вот обновленный код:

public static List<Integer> caculateSum(BinaryTree root) {
    List<Integer> sums = new ArrayList<>();
    int sum=0;
    BinaryTree current = root, popped=null;
    Stack<BinaryTree> s = new Stack<BinaryTree>();
    while(current!=null ) {
        //checking if last node popped from stack is not equal to left or right node of current node
        if(popped==null||((current.left!=null && !current.left.equals(popped)) && (current.right!=null && !current.right.equals(popped)))) {
            while(current != null) {
                sum+=current.value;
                s.push(current);
                current = current.left;

            }
        }
        current=s.peek();
        if(current.right == null) {
            //if current node is leaf node
            if(current.left == null) {
                sums.add(sum);
            }
            sum-=current.value;
            popped = current;
            s.pop();
        } else if(current.right!=null && current.right.equals(popped)){
            //if current node both left and right nodes have been processed
            sum-=current.value;
            popped = current;
            s.pop();
        }else {
            //if current node right part is not processed
            sum+=current.right.value;
            s.push(current.right);  
        }
        if(s.isEmpty()) {
            break;
        }
        current=s.peek();       
    }   
    return sums;
}

Поясню это на примере. Предположим, что мы дали двоичное дерево

1,2,9,3,7, null, 8,5

Здесь, в приведенном выше коде, кроме старых переменных, используется новая переменная popped, которая отслеживает последний элемент, который выскочил из стека .

Итак, вот основные шаги:

1. Начиная с узла current, мы находимся проверка, не равен ли текущий узел слева попопу (если он равен, это означает, что левая часть узла current уже обработана, поэтому нам не нужно обрабатывать его снова). То же самое мы проверяем, если правый узел current узла не равен узлу popped (если он равен, это означает, что мы уже обработали правый узел узла current, что косвенно означает, что узел left также обрабатывается).

2. Теперь для верхнего узла стека, который является current узлом, мы проверяем:

   • Если его узел right равен нулю Если это правда, это означает либо узел current является конечным узлом, либо это уже обработанный узел, чей узел right является нулевым (как в нашем примере узла со значением 3). Если это лист, мы добавляем его в наш список sums. Кроме того, в обоих случаях мы удаляем этот узел top и вычитаем его значение из текущего значения sum (это было сделано и в приведенном выше коде). Наряду с этим мы будем отслеживать извлеченный элемент из стека в popped variable.

   • Если его право не равно нулю, но его узел right равен узлу popped Это происходит, когда на последнем проходе в то время как l oop мы обработали это right узел. Это означает, что для верхнего узла стека были обработаны как левый, так и правый узлы, и, следовательно, мы извлекаем этот узел и отслеживаем его в переменной popped.

   • Иначе мы pu sh правый узел верхнего элемента стека в стеке.

В конце вышеприведенного примера переменная sums сохранит результат как [11, 10, 18 ]