二叉树的垂直和

Problem statement: Given a binary tree, find the vertical sum for the binary tree along each vertical line.

问题陈述：给定一棵二叉树，沿着每条垂直线找到二叉树的垂直和。

Solution:

解：

First we need to understand what vertical sum is. Let go through an example to understand what vertical sum is.

首先，我们需要了解什么是垂直和。 让我们通过一个例子来了解什么是垂直和。

For the above tree, let's check what the vertical sum is for the tree.

对于上面的树，让我们检查一下树的垂直和。

Just consider, we have partitioned the tree nodes into column & rows where rows are the level no starting from 0. Then the above tree can be converted into the above table easily.

考虑一下，我们将树节点划分为列和行，其中行是从0开始的级别。然后，可以将上面的树轻松转换为上面的表。

1. Start from root. Root column is 0.

   从根开始。 根列为0。

2. If next node is at left of current node

   如果下一个节点在当前节点的左侧

   Then column of next node=column of current node-1

   然后，下一个节点的列=当前节点-1的列

   Else

   其他

   Column of next node=column of current node+1

   下一个节点的列=当前节点的列+1

Using the above steps the tree can be easily partitioned to the table. It is to observe that there may be several entry at a specific (row, column) position. Like here, at Level3, column no 1 has two entry 4 & 11.

使用上述步骤，可以轻松地将树分区到表中。 可以观察到在特定(行，列)位置可能有多个条目。 像这里一样，在Level3，第1列有两个条目4和11。

Rest is about doing sums for each column and printing it.

剩下的就是为每一列求和并打印出来。

Thus the vertical sum output should be 2, 12, 8, 20, 9 (from col -2 to col 2 direction).

因此，垂直和输出应为2、12、8、20、9(从col -2到col 2方向)。

Though the visual description seems to be very easy to solve this problem, in programing view it’s not that easy.

尽管视觉描述似乎很容易解决此问题，但在编程视图中并不是那么容易。

求垂直和的算法 (Algorithm to find vertical sum)

The basic concept is to do pre-order traversal & while traversing we will keep track for each column (hashing)& will find cumulative sum.

基本概念是进行预遍历和遍历，我们将跟踪每列(散列)并找到累积和。

Thus the column is used as key & we need a map to process our algorithm.

因此，该列用作键 ，我们需要一个映射来处理我们的算法。

1. Initialize map<int, int>hash. //(ordered map)

   初始化map <int，int> hash 。 //(有序地图)

2. Start from root. Column for root is 0.

   从根开始。 根的列为0。

   Call vertical_sum(root, 0, hash);

   调用vertical_sum(root，0，hash);

3. Recursive function

   递归函数

4. Function vertical_sum( tree node, column, reference of map hash)a) If (node== NULL)        Return;//hash[column]+=node->datab) Add node value cumulatively for the column; // vertical_sum(node->left, column-1, reference of map hash)c) Recursive do for the left subtree; We are passing col-1 since it’s on the left// vertical_sum(node->right, column+1, reference of map hash)d) Recursive do for the right subtree; We are passing col+1 since it’s on the rightEnd Functionvertical_sum;

5. Print the hash map to output the vertical sums for corresponding column.

   打印哈希图以输出对应列的垂直和。

C ++实现打印二叉树的垂直和 (C++ implementation to print vertical sum of a binary tree)

#include 
    
     using namespace std;// tree node is definedclass tree{
   	public:		int data;		tree *left;		tree *right;};//finding vertical sumvoid findVerticalSum(tree* root,int col,map
     
       &hash){
    	if(root==NULL) //base case		return;	//finding sum for respecting column, hashing the column	hash[col]+=root->data; 	//recursively process left sub-tree	findVerticalSum(root->left,col-1,hash); 	//recursively process right sub-tree	findVerticalSum(root->right,col+1,hash); }void vertical_sum(tree* root){
   	//ordered hash map	map
      
        hash; 	//column no for root is 0	findVerticalSum(root,0,hash); 	cout<<"column"<<"\t"<<"sum\n";	//printing the values from hash map	for(auto it=hash.begin();it!=hash.end();it++){
    		//it->first= column no(key) , 		//it->second=vertical sum of respective column(value)		cout<
       
        first<<"\t"<
        
         second<
         
          data = data; node->left = NULL; node->right = NULL; return(node); } int main() { //**same tree is builted as shown in example** int c,K; cout<<"Tree is built like the example aforesaid"<
          
           left= newnode(7); root->right= newnode(5); root->right->right=newnode(9); root->right->right->left=newnode(4); root->left->left=newnode(2); root->left->right=newnode(6); root->left->right->left=newnode(5); root->left->right->right=newnode(11); cout<<"finding vertical sums......"<
          
         
        
       
      
     
    

Output

输出量

Tree is built like the example aforesaidfinding vertical sums......column  sum-2      2-1      120       81       202       9

翻译自:

二叉树的垂直和