二叉树的垂直和[关闭]

如何求二叉树的垂直和。

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

                      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

首先，您应该找到位置，您可以通过计算到达特定节点的左右花费数量来完成此操作：

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

只需遍历二叉树并最终计算LorR = NumberOfLeft - NumberOfRights对于每个节点，然后将这些数字分组（按它们的LorR值）在一起并找到每个组的总和（从最大正值到最大负值打印它们LorR).

Update:这不适用于高度超过二的树，我们只需对算法进行少量修改即可解决此问题。

我们可以将树视为金字塔，金字塔的每个顶点的长度为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 中，依此类推。

For preventing from rounding of 1/(2^x) to zero or other problems we can multiply our factors (1/2, 1/4, 1/8,...) to 2^h-1. In fact in the first case I wrote we can say factors are multiplied by 2^2-1.