algorithm - 给定一个树结构，你如何使用递归将它变成一个简单的链表？

Question

给定一棵二叉树(只有左 child 和右 child )，如何编写递归函数使其就地成为简单的链表？ (不应创建新的数据结构。伪代码就可以)。假设每个节点都有一个整数值，比如 123，或 2，或 3。最终的链表应该包含树中的所有节点。顺序并不重要。

更新:需要就地进行。不应创建新的数据结构。

Answer 1

总是有不同的方法来遍历树，例如:

• 按顺序
• 预购
• 下单

您可以选择其中任何一个来组成您的列表...

例如(伪代码，PreOrder):

function treeToList(LinkedList l, Tree t)
    if(t not nil)
        l.add(t.element)
        treeToList(l, t.Left)
        treeToList(l, t.Right)
    endif
end function

记住:如果您在二叉搜索树上执行 InOrder，您将获得排序后的元素。