数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装学
法律研究用 C++ 找出二叉树中最大的垂直和
假设我们有一棵二叉树。任务是打印垂直次序遍历中所有节点和的最大值。因此，如果树如下所示 −
垂直次序遍历如下所示 −
4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9
最大值为 12。方法很简单。我们将执行垂直次序遍历，然后求和并检查最大值。
示例
#include<iostream>
#include<map>
#include<vector>
#include<queue>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node* getNode(int key){
Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
return node;
}
int getMaxSum(Node* root) {
if (!root)
return -1;
int n = 0;
int k_node = -1;
map<int, vector<int> > current_map;
int hd = 0;
queue<pair<Node*, int> > que;
que.push(make_pair(root, hd));
while (!que.empty()) {
pair<Node*, int> temp = que.front();
que.pop();
hd = temp.second;
Node* node = temp.first;
current_map[hd].push_back(node->key);
if (node->left != NULL)
que.push(make_pair(node->left, hd - 1));
if (node->right != NULL)
que.push(make_pair(node->right, hd + 1));
}
map<int, vector<int> >::iterator it;
int maximum = INT_MIN;
for (it = current_map.begin(); it != current_map.end(); it++) {
int temp_sum = 0;
for (int i = 0; i < it->second.size(); ++i) {
temp_sum += it->second[i];
}
if(maximum < temp_sum){
maximum = temp_sum;
}
}
return maximum;
}
int main() {
Node* root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->right->left->right = getNode(8);
root->right->right->right = getNode(9);
cout << "Maximum sum of vertical nodes: " << getMaxSum(root);
}输出
Maximum sum of vertical nodes: 12
更新日期：2019 年 12 月 18 日
85 次查看
广告