algorithm - 如何计算预序树数组中节点的深度？

Question

例如，一棵树

             2
           /   \
          1     3
         / \   / \
       null n n   null

存储为一个数组，顺序为:[2, 1, null, null, 3, null, null]。你如何计算节点的深度？或者如何将预订转换为深度优先？

Answer 1

仅考虑预序遍历，这是不可能的。以你的例子为例:

[2, 1, null, null, 3, null, null]

重建一棵树有几种可能的解决方案。这里有两个:

         2
       /   \
      1     3
     / \   / \
   null n n   null

         2
       /   \
      1     3
     /     / \
   null   n   null
   /
 null

要重建树，您还需要后序。然后您可以点击下一个链接找到解决方案:http://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/