Максимальная сумма пути в двоичном дереве, не рекурсивная, превышен лимит времени
Я борюсь с этой проблемой, которую хочу решить нерекурсивным способом. Кажется, в моем алгоритме нет логической ошибки, пройдено 73% тестов. Но он не может обрабатывать большие данные, сообщается "Превышен лимит времени". Я ценю, если кто-нибудь может дать мне подсказку, как сделать это нерекурсивно и избежать превышения лимита времени, заранее спасибо!
Проблема Ссылка
Я полагаю, что в LeetCode есть аналогичный.
http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/
Описание проблемы:
По заданному бинарному дереву найдите максимальную сумму пути от корня. Путь может заканчиваться на любом узле дерева и содержать в нем хотя бы один узел.
Пример:
Учитывая приведенное ниже двоичное дерево:
1
/ \
2 3
вернуть 4. (1->3)
судья
Превышен лимит времени
Общее время выполнения: 1030 мс
Входные данные
{-790,-726970696, -266, -545830, -866669, -488, -122260116521,-866,-480,-573,-926,88,733,#,#,483,-935,-285,-258892180279,-935,675,2,596,5,50,830,-607,-212,663,25,-840,#,#,-333754,# 817842, -220, -269,9, -862, -78, -473643536, - 142.773.485.262.360.702, -661244,-96,# 519566, -893, -599126, -314160358159,#,#,-237,-522,-327310, -506462, -705868, -782300, -945, -3139, - 193, -205, -92795, -99, -983, -658, -114, -706 987 292,# 234, -406, -993, -863859875383, -729, -748, -258 329 431, -188, -375, -696, -856825, -154, -398, -917, -70105819, -264,993,207,21, -102,50,569, -824, -604895, -564, -361 110, -965, -11557,# 202213,-141,759,214,207,135,329,15,#,#,244,#,334628509627, -737, -33, -339, -985 349 267, -505, -527 882, -352, -357, -630 782, -215, -555 132, - 835, -421,751,0, -792, -575, -615, -690718248882, -606, -53157750862,#,940,160,47,-347,-101,-947739894,#,- +658, -90, -277, -925997862, -481, -83708706686, -542485517, -922978, -464, -923710, -691168, -607, -888, -439499794, -601435, -114, -337422,#,-855,-859163,-224,902,#,577,#,-386,272,-9 ...
ожидаемый
6678
Мой код C++
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root the root of binary tree.
* @return an integer
*/
int maxPathSum2(TreeNode *root) {
if (root == NULL) return 0;
findLeaf(root);
return global_max;
}
private:
int global_max = INT_MIN;
void findLeaf(TreeNode* root) {
unordered_map<TreeNode*, TreeNode*> parent;
stack<TreeNode*> traverse;
parent[root] = NULL;
traverse.push(root);
while(!traverse.empty()) {
TreeNode* p = traverse.top();
traverse.pop();
if (!p->left && !p->right) {
findPathMaxSum(p, parent);
}
if (p->right) {
parent[p->right] = p;
traverse.push(p->right);
}
if (p->left) {
parent[p->left] = p;
traverse.push(p->left);
}
}
}
void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*> parent) {
TreeNode* current = leaf;
stack<TreeNode*> stk;
int path_max = INT_MIN;
int path_sum = 0;
while (current) {
stk.push(current);
current = parent[current];
}
while (!stk.empty()) {
current = stk.top();
stk.pop();
path_sum += current->val;
path_max = path_max > path_sum ? path_max : path_sum;
}
global_max = global_max > path_max ? global_max : path_max;
}
};
РЕШИТЬ
Я принимаю совет @Dave Galvin, и он работает! Вот код:
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root the root of binary tree.
* @return an integer
*/
int maxPathSum2(TreeNode *root) {
if (root == NULL) return 0;
int global_max = INT_MIN;
stack<TreeNode*> traverse;
traverse.push(root);
while(!traverse.empty()) {
TreeNode* p = traverse.top();
global_max = global_max > p->val ? global_max : p->val;
traverse.pop();
if (p->right) {
traverse.push(p->right);
p->right->val += p->val;
}
if (p->left) {
traverse.push(p->left);
p->left->val += p->val;
}
}
return global_max;
}
};
3 ответа
Сверху вниз обновите каждый узел, добавив к нему значение его родителя. Следите за своим максимальным значением и его положением. Верните это в конце. На).
Например, если ваше двоичное дерево имеет вид T=[-4,2,6,-5,2,1,5], то мы обновляем его как: [-4, 2-4=-2, 6-4=2, -2-5 = -7, -2+2=4, 2+3=3, 2+5=7]
Здесь ответ 7, собирается -4, 6, 5.
Я предполагаю, что проблема с вашим кодом заключается в том, что когда вы пересекаете свое дерево, в каждом узле вы выполняете итерацию для вычисления максимального пути. Это заканчивается сложностью O(n^2), Вам необходимо рассчитать максимальный путь потока (при обходе дерева).
В приведенном ниже решении я использовал итерационный алгоритм после заказа. Пожалуйста, прости меня, что я использовал этот вместо твоего.
Решение (O(n)) просто добавить поле max_path к каждому узлу, и при посещении фактического узла взять максимум между left а также right:
void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr = s.top();
if (!prev || prev->left == curr || prev->right == curr) {
if (curr->left)
s.push(curr->left);
else if (curr->right)
s.push(curr->right);
} else if (curr->left == prev) {
if (curr->right)
s.push(curr->right);
} else {
//Visiting the node, calculate max for curr
if (curr->left == NULL && curr->right==NULL)
curr->max_path = curr->data;
else if (curr->left == NULL)
curr->max_path = curr->right->max_path + curr->data;
else if (curr->right == NULL)
curr->max_path = curr->left->max_path + curr->data;
else //take max of left and right
curr->max_path = max(curr->left->max_path, curr->right->max_path) + curr->data;
s.pop();
}
prev = curr;
}
}
Редакция:
вам не понадобится функция findPathMaxSum. Я также изменил родительскую карту. Теперь он хранит 2 значения:
- указатель на родителя
- сумма пути от корня до текущего узла.
Вот код
class Solution {
public:
/**
* @param root the root of binary tree.
* @return an integer
*/
int maxPathSum2(TreeNode *root) {
if (root == NULL) return 0;
findLeaf(root);
return global_max;
}
private:
int global_max = INT_MIN;
void findLeaf(TreeNode* root) {
unordered_map<TreeNode*, std::pair<TreeNode*,int> > parent;
stack<TreeNode*> traverse;
parent[root] = make_pair(NULL,root->val);
traverse.push(root);
while(!traverse.empty()) {
TreeNode* p = traverse.top();
traverse.pop();
if (!p->left && !p->right) {
// findPathMaxSum(p, parent);
global_max=std::max(global_max,parent[p].second);
}
if (p->right) {
parent[p->right] = make_pair(p, (p->right->val) +parent[p].second) ;
traverse.push(p->right);
}
if (p->left) {
parent[p->left] = make_pair(p, (p->left->val) +parent[p].second) ;
traverse.push(p->left);
}
}
};
OLD:
Вы хотите передать карту по ссылке, а не по значению в findPathMaxSum.
void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*> parent)
измените это на.
void findPathMaxSum(TreeNode* leaf, unordered_map<TreeNode*, TreeNode*>& parent)
Это делает вашу временную сложность O(n*n).
Его сложность запуска станет O(n*log n). Хотя это не сработало, так как ваши ограничения более жесткие. Поэтому я разместил решение O(n) выше.