二叉树的垂直总和

Question

如何找到二叉树的垂直和.

例如,考虑下面的二叉树,

                      1
                    /  \
                   /    \
                  /      \
                 2        3
                / \      / \
               /   \    /   \
               4   5    6    7
              / \ / \  / \  / \
             5  9 1  3 6 7 5   5

对于上面的树,垂直和应该计算如下,

• 1:5行
• 2号线:4
• 第3行:2,9,1
• 第4行:5
• 第5行:1,3,6
• 6号线:6
• 7号线:3,7,5
• 8号线:7
• 9号线:5

输出应该是:

5,4,12,5,10,6,15,7,5

Answer 1

首先你应该找到这些位置,你可以通过计算剩余数量和权利支出来到达特定节点:

                 1     : l = 0, r = 0
                / \
               /   \
      l=1,r=0 2     3  : l = 0, r = 1.
             / \   / \
     ...    4...5 6...7 ....

简单地说,您可以遍历二叉树并最终计算LorR = NumberOfLeft - NumberOfRights每个节点,然后将这些数字(按其LorR值)组合在一起,找到每个组的总和(从最正值到最负值打印它们LorR).

更新:这对于高度超过2的树没有答案,我们可以通过算法中的少量修改来解决这个问题.

我们可以看到树作为金字塔,金字塔的每个顶点都有长度1,在每个分支剩余部分的分支等于最新移动中传递的内容之后,我们在图片中显示高度为3的树:

                  1
                /  \
               /    \
              /      \
             2        3    upto this we used 1/2 size of pyramid
            / \      / \
           /   \    /   \
           4   5    6    7  upto this we used 1/2 + 1/4 part of pyramid
          / \ / \  / \  / \
         5  9 1  3 6 7 5   5  upto this we used 1/2 + 1/4 + 1/4 part of pyramid

这意味着在每个步骤中我们通过它们的高度计算左值(实际上每次乘以1/2将乘以左值,除了上一次,它等于h-1 st值).

因此,对于这种情况,我们有:1在根中是在组0中,3在叶中是在组-1/2 + 1/4 + 1/4 = 0,6中在叶中是在组1/2 - 1/4 - 1/4 = 0

叶子中的1是-1/2 + 1/4 - 1/4 = -1/2,依此类推.

为了防止1 /(2 ^ x)舍入到零或其他问题,我们可以将我们的因子(1/2,1/4,1/8,...)乘以2 ^h-1.事实上,在我写的第一个案例中,我们可以说因子乘以2 ^2-1.