Суммирование элементов в дереве

Опубликовано Sep 30, 2011 в Деревья и графы | Нет комментариев

, ,

Дано отсортированное бинарное дерево, содержащее положительные целые числа с узлами заданной структуры. Реализовать метод, который бы вернул все пути в этом дереве, с суммой равной заданному числу. Путь не обязательно должен начинаться от корня дерева.

C++                                           C#
struct tree_node                              public class Node
{                                             {
    tree_node* left;                             public Node Left;
    tree_node* right;                            public Node Right;
    int data;                                    public int Data;
}                                              } 

//Ваш код                                      //Ваш код

Критерии оценки FulcrumWeb:

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

Ожидаемые вопросы:

  1. Что значит вернуть все пути? Достаточно ли вернуть значения данных из узлов в правильном порядке или нужно вернуть указатели(ссылки) на узлы, то есть все поддерево? Или нужна новая динамическая структура с полным копированием данных и организацией собственных связей?
  2. C++: Я собираюсь использовать динамические контейнеры STL. Есть ли ограничения на их применение?
  3. C++: Я собираюсь организовать линейный односвязный список для возврата результата. Можно ли использовать для узла этого списка готовую структуру данных, оставив в ней одну из связей пустой, или создать новую структуру для этого?
  4. C#: Можно ли описать дерево в XML формате и работать с ним соответствующими средствами? Поддеревья, получаемые на выходе, при этом тоже будут выдаваться как XML.

Оценка результатов:

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

В решении на C++ обязательно не должно быть утечек памяти.

От более опытных кандидатов ожидаются вопросы, которые позволят увидеть понимание возможности решить задачу с использованием динамических контейнеров из STL. Если будет представлено решение, основанное на самостоятельной организации выходной структуры данных, то вопрос об STL будет поднят интервьюером.