获取二叉树的国彩网和

问题陈述：

给您一个根节点，您需要计算树的国彩网和。

考虑下图

国彩网线1：只有一个节点7 => vertical sum is 7
国彩网线2：只有一个节点10 => vertical sum is 10
国彩网线3：具有三个节点：16、15、18 =>国彩网总和为16 + 15 + 18 = 49
国彩网线4：只有一个节点25 => vertical sum is 25
国彩网线5：只有一个节点30 => vertical sum is 30

所以输出应该是7、10、49、25、30

解：

解决方案非常简单。

我们需要为每个节点计算HD，并添加水平距离相同的节点值。

我们需要对遍历进行排序。

C ++解决方案

#include <iostream>
#include <map>
#include <vector>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


void get_vertical_sum(Node *node, int hd, map<int, int> &myMap) 
{ 
    if (node == NULL) 
        return; 
  
    get_vertical_sum(node->left, hd-1, myMap); 
  
    myMap[hd] += node->data; 
  
    get_vertical_sum(node->right, hd+1, myMap); 
} 

  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    map < int, int> myMap; 
    map < int, int> :: iterator it; 

    get_vertical_sum(root, 0, myMap);

    for (it = myMap.begin(); it != myMap.end(); ++it) 
    { 
        cout << it->first << ": "
             << it->second << endl; 
    } 

    return 0;  
}

输出：

-2: 7
-1: 10
0: 49
1: 25
2: 30