Как написать рекурсивную функцию, которая возвращает связанный список узлов, когда задано двоичное дерево узлов?

Question

Меня однажды спросили об этом в интервью:

Как написать рекурсивную функцию, которая возвращает связанный список узлов, когда дано двоичное дерево узлов? (выравнивание данных) ( Обновление: как насчет, не просто проходите по дереву и добавляйте узлы в глобальную структуру. Сделайте функцию полностью рекурсивной и модифицируйте двоичное дерево на месте)

По какой-то причине мне, как правило, требуется от 3 до 5 минут, чтобы решить любую рекурсивную проблему. Обычно 15-20 минут будут более похожими. Как мы можем атаковать эту проблему, такую ​​как очень систематический способ достижения решения, чтобы их можно было решить за 3-5 минут?

Answer 1

Почти то, что сделал @vittore, но с распределением по одному списку (но он будет перераспределен внутри, так что ..). Это также вероятно (неисправность мозга) в порядке.

public List<Tree> Flat(List<Tree> t)
{
    var t = t ?? new List<Tree>();
    Left != null ? Left.Flat(t):;        
    t.Add(this);        
    Right != null ? Right.Flat(t):;
    return t;
}

Answer 2

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

Предположим, у вас есть класс Node с полями value, leftChild и rightChild. Пример кода Java для обхода leftchild-parent-rightchild:

public List<Node> traverseTree (Node parentNode) {
   List<Node> nodes = new LinkedList<Node> ();
   if (parentNode.hasLeftChild ()) {
      nodes.addAll (traverseTree (parentNode.getLeftChild ()));
   }
   nodes.add (parentNode);
   if (parentNode.hasRightChild ()) {
      nodes.addAll (traverseTree (parentNode.getRightChild ()));
   }
   return nodes;
}

Answer 3

Вот так

public class Tree
{
    public Tree Left { get; set; }
    public Tree Right { get; set; }

    public List<Tree> FlatTree()
    {
        var list = new List<Tree>();
        list.Add(this);
        if (Left!=null) list.AddRange(Left.FlatTree());
        if (Right!= null) list.AddRange(Right.FlatTree());
        return list;
    }
}

добавь себя, добавь левую ветвь польщенную, добавь правую ветвь польщенную

Answer 4

Как насчет "создать связанные списки двух ветвей, а затем добавить одну к другой"?

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