我正在努力解决这个问题,希望以非递归的方式解决。我的算法似乎没有逻辑错误,通过了73%的测试用例。但它无法处理大数据,报告“时间限制超出”。如果有人能给我一些提示如何以非递归的方式避免时间限制,我将不胜感激,谢谢!
问题链接
我相信在LeetCode中也有一个类似的问题。
http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/
问题描述:
给定一个二叉树,找到从根节点开始的最大路径和。 路径可以在树中的任何节点结束,并且其中至少包含一个节点。
示例:
给定以下二叉树:
1
/ \
2 3
返回4。(1->3)
判定
时间限制超出
总运行时间:1030毫秒
输入 输入数据
预期结果:
6678
代码:
{-790,-726,970,696,-266,-545,830,-866,669,-488,-122,260,116,521,-866,-480,-573,-926,88,733,#,#,483,-935,-285,-258,892,180,279,-935,675,2,596,5,50,830,-607,-212,663,25,-840,#,#,-333,754,#,817,842,-220,-269,9,-862,-78,-473,643,536,-142,773,485,262,360,702,-661,244,-96,#,519,566,-893,-599,126,-314,160,358,159,#,#,-237,-522,-327,310,-506,462,-705,868,-782,300,-945,-3,139,-193,-205,-92,795,-99,-983,-658,-114,-706,987,292,#,234,-406,-993,-863,859,875,383,-729,-748,-258,329,431,-188,-375,-696,-856,825,-154,-398,-917,-70,105,819,-264,993,207,21,-102,50,569,-824,-604,895,-564,-361,110,-965,-11,557,#,202,213,-141,759,214,207,135,329,15,#,#,244,#,334,628,509,627,-737,-33,-339,-985,349,267,-505,-527,882,-352,-357,-630,782,-215,-555,132,-835,-421,751,0,-792,-575,-615,-690,718,248,882,-606,-53,157,750,862,#,940,160,47,-347,-101,-947,739,894,#,-658,-90,-277,-925,997,862,-481,-83,708,706,686,-542,485,517,-922,978,-464,-923,710,-691,168,-607,-888,-439,499,794,-601,435,-114,-337,422,#,-855,-859,163,-224,902,#,577,#,-386,272,-9 ...
/**
* 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;
}
};