二叉树的垂直总和 [英] 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号线：6
• 7号线：3,7,5
• 行8：7
• 线路9：5

输出应该是：

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

解决方案

首先，你应该找到的位置，你可以通过计算左，权利花费达到特定的节点数量做到这一点：

  1：L = 0，R = 0
                / \
               / \
      升= 1，R = 0 2 3：升= 0，R = 1。
             / \ / \
     ... 4 ... 5 6 ... 7 ....
 

只要你可以遍历您的二叉树最后计算出 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次值）。

因此​​，对于这种情况下，我们有：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等

。

有关从舍入preventing 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 2^h-1. In fact in the first case I wrote we can say factors are multiplied by 2^2-1.

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