Сгладить двоичное дерево -> Единый связанный список (Ruby)

Question

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

Given a binary tree, flatten it to a linked list in-place. 

For example, 
Given 

     1 
     /\ 
     2 5 
    /\ \ 
    3 4 6 
The flattened tree should look like: 
    1 
    \ 
    2 
     \ 
     3 
     \ 
     4 
      \ 
      5 
      \ 
      6 

Я написал следующий рекурсивный код, который просто не работает (возвращает неправильный ответ), но я не могу концептуально понять, почему нет. Начиная с корня, мы сглаживаем root.left и root.right. Если root.left существует, то root.next (или в этом случае root.right) укажет на сплющенный левый список. Затем левый список указывает на начало правого списка. Это продолжается рекурсивно вниз по дереву.

Что-то не так с этим концептуально? Я попробовал моделировать его после обхода предварительного заказа, так как по существу посещается корень, затем слева, а затем справа.

def flatten(root) 
    return root if root.nil? 
    left_list = flatten(root.left) 
    right_list = flatten(root.right) 
    root.left = nil 


    root.right = (left_list.nil? ? right_list : left_list) 
    find_tail(left_list).right = right_list unless left_list.nil? 
end 

def find_tail(node) 
    return nil if node.nil? 
    until node.right.nil? 
     node = node.right 
    end 

    node 
end 

Answer 1

Ваш flatten не возвращает то, что он должен. Это имеет значение, поскольку вы называете это рекурсивно. Измените его на

... 
    find_tail(left_list).right = right_list unless left_list.nil? 
    root # <-- add this line 
end