打印二叉树的边界

Question

如何打印二叉树的外框.

1. 订单从上到下,从左到右,然后从下到上
2. 打印所有leftest节点和最正常的节点
3. 打印所有叶节点

4. 打印只有1个叶子的所有节点

            100
           /   \ 
         50     150
        / \      /
      24   57   130
     /  \    \    \
   12   30    60   132
   

例如:输出应为100,50,24,12,30,57,60,130,132,150

如果我们编写三个不同的函数来打印左节点,叶节点和右节点,它可以很容易地解决,但需要O(n + 2logn)时间.

我也在寻找O(n)方法,但条件是每个节点只应访问一次,不需要额外的O(2logn)部分.

Answer 1

您可以通过将 Euler Tour 算法应用于您的树来实现这一点。请参阅此链接：

或者（如果可以访问的话）古德里奇等人的书。al（链接。此处）

我希望这有帮助