Максимальная сумма пути в двоичном дереве, не рекурсивная, превышен лимит времени
Я борюсь с этой проблемой, которую хочу решить нерекурсивным способом. Кажется, в моем алгоритме нет логической ошибки, пройдено 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;
}
};
Решение
Сверху вниз обновите каждый узел, добавив к нему значение его родителя. Следите за своим максимальным значением и его положением. Верните это в конце. На).
Например, если ваше двоичное дерево имеет вид 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) выше.