我正在努力解决这个问题,我想以非递归方式解决这个问题。 在我的算法中似乎没有逻辑错误,通过了73%的测试用例。 但它无法处理大数据,报告“超出时间限制”。 我很感激,如果有人可以给我一些提示如何在非递归的情况下做到这一点,并避免超时,请提前致谢!
问题链接
我相信在LeetCode中也有类似的情况。
http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/
问题描述:
给定一个二叉树,从根中找出最大路径和。 该路径可能会在树中的任何节点处结束,并且至少包含一个节点。
例:
鉴于下面的二叉树:
1
/ \
2 3
返回4.(1-> 3)
法官
超时限
总运行时间:1030毫秒
输入输入数据
{-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,#,#, - 333754,#817842,-220,-269,9,-862,-78,-473,643,536 - 142,773,485,262,360,702,-661,244,-96,#519566,-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,#,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,-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 ...
预期
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; } };I'm struggling with this problem, which I want to solve in non-recursive way. There seems no logic error in my algorithm, 73% test cases passed. But it can't handle the big data, reported "Time Limit Exceeded". I appreciate if somebody could give me some hint how to do it in non-recursive and avoid time limit exceed, thanks in advance!
Problem Link
I believe there's also a similar one in LeetCode.
http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/
Problem description:
Given a binary tree, find the maximum path sum from root. The path may end at any node in the tree and contain at least one node in it.
Example:
Given the below binary tree:
1
/ \
2 3
return 4. (1->3)
Judge
Time Limit Exceeded
Total Runtime: 1030 ms
Input Input Data
{-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 ...
Expected
6678
My Code 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; } };SOLVED
I accept the advice by @Dave Galvin and it works! Here's the code:
/** * 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。
From the top down, update each node by adding its parent's value to it. Keep track of your max value and its position. Return that at the end. O(n).
E.g., if your binary tree is T=[-4,2,6,-5,2,1,5], then we update it as: [-4, 2-4=-2, 6-4=2, -2-5 = -7, -2+2=4, 2+3=3, 2+5=7]
Here the answer is 7, going -4, 6, 5.
更多推荐
发布评论