压平树

Question

扁平化数据：当给定节点的二叉树时，如何编写返回节点链表的递归函数？（树可以修改）

在这个提问中，压扁树是什么意思？我们是否需要使用左右指针将二叉树的所有元素保存在列表中，或者还有另一个我没有得到的捕获？

其次（树可以修改）他们是否意味着乐趣应该能够处理树的任何修改以及构建？

Answer 1

假设你有一个像这样的二叉树：

    a
   / \
  b   c
 / \   \
0   0   d
       / \
      0   0

其中a、b等是节点并且0为零。树有几种可能的递归遍历：

• 在孩子之前预购，拜访父母： a b c d

• 按顺序，在孩子之间访问父母： b a c d

• 订购后，在孩子之后拜访父母： b d c a

树的“扁平化”仅仅是遍历产生的一个列表；您的数据结构不再是嵌套的，而是扁平的。要展平一棵树，请从一个空的链表开始。然后按照您选择的顺序遍历树，将每个访问过的节点附加到链表中。我认为“可以修改树”意味着您的函数可能会在构建列表时更改树，如果您认为有必要这样做的话。