Cho cây nhị phân, tìm max tổng các nút trong cùng cột dọc (vertical order). Ví dụ cây cho trước, tổng dọc: 4, 2, 1+5+6=12, 3+8=11, 7, 9 → max=12.
Thực hiện duyệt dọc bằng hàng đợi và map theo độ ngang hd. Tính tổng từng cột, lấy max.
Ví dụ
#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); }
Kết quả
Maximum sum of vertical nodes: 12