二叉树的垂直和 [英] Vertical sum of a binary tree

问题描述

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

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

  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行：第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： = 0，r = 1. 
 / \ / \ 
 ... 4 ... 5 6 ... 7 .... 
  / pre> 
 
 
只需遍历二叉树，最后计算每个节点的$ code> LorR = NumberOfLeft  -  NumberOfRights ，然后将这个数字（通过他们的 LorR 值）组合在一起，并找到每个组合的总和（将它们从最正值到最负的值 LorR ）。
 
 
 
 更新：这个高度不超过两个的树不能解答，我们可以修改这个问题在算法中。
 
 
 
我们可以看到树为金字塔，金字塔的每个顶点的长度为1，每个分支后面分支部分等于最新动作通过的内容，我们在高度3树中显示此图：
  1 
 / \ 
 / \ 
 / \ 
 2 3至此我们使用1/2尺寸的金字塔
 / \ / \ 
 / \ / \ 
 4 5 6 7至此我们使用了1/2 + 1/4金字塔
 / \ / \ / \ / \ 
 5 9 1 3 6 7 5 5至此我们使用1/2 + 1/4 + 1/4金字塔
  
 
 
这意味着在每个步骤中，我们按照它们的高度计算左值（实际上每次乘以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 。 
 
 
 
  
How to find the vertical sum of a binary tree.

For example,
Consider the binary tree below,
                      1
                    /  \
                   /    \
                  /      \
                 2        3
                / \      / \
               /   \    /   \
               4   5    6    7
              / \ / \  / \  / \
             5  9 1  3 6 7 5   5
For the above tree, Vertical sum should be calculated as follows,


Line 1: 5
Line 2: 4
Line 3: 2,9,1
Line 4: 5
Line 5: 1,3,6
Line 6: 6
Line 7: 3,7,5
Line 8: 7
Line 9: 5


Output should be:
5,4,12,5,10,6,15,7,5

解决方案
First you should find the positions, you can do this by counting number of left and rights spend to reach specific node:
                 1     : l = 0, r = 0
                / \
               /   \
      l=1,r=0 2     3  : l = 0, r = 1.
             / \   / \
     ...    4...5 6...7 ....
Simply you can traverse your binary tree and finally calculate LorR = NumberOfLeft - NumberOfRights for each node, then group this numbers (by their LorR value) together and find each groups sum (print them from most positive to most negative value of LorR).

Update: This doesn't answers for tree of height more than two, we can fix this problem with little modification in algorithm.

We can see tree as pyramid, each vertex of pyramid has length 1, after each branch remaining part of branch is equal to what passed in latest move, we show this in picture for tree of height 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
This means in each step we calculate left values by their height (in fact each time multiply of 1/2 will be added to left value, except last time, which is equal to h-1 st value).

So for this case we have: 1 in root is in group 0, 3 in leaf is in group -1/2 + 1/4 + 1/4 = 0, 6 in leaf is in group 1/2 -  1/4 - 1/4 = 0

1 in leaf is in -1/2 + 1/4 - 1/4 = -1/2 and so on.

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 2h-1. In fact in the first case I wrote we can say factors are multiplied by 22-1.  



                        
这篇关于二叉树的垂直和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！