二叉树的垂直和

首先，您应该找到头寸，您可以通过计算到达特定节点的左侧和右侧花费的数量来做到这一点：

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


只需简单地遍历二叉树并最终LorR = NumberOfLeft -
NumberOfRights为每个节点进行计算，然后将此数字（按其LorR值）分组并找到每个组的总和（将的值从的最大正值打印到最大的负值LorR）即可。

这不能解决高度超过两棵树的问题，我们只需对算法进行少量修改就可以解决此问题。

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