二叉树最大路径总和，非递归，超出时间限制(Binary Tree Maximum Path Sum, non

二叉树最大路径总和，非递归，超出时间限制(Binary Tree Maximum Path Sum, non-recursive, Time Limit Exceeded)

我正在努力解决这个问题，我想以非递归方式解决这个问题。在我的算法中似乎没有逻辑错误，通过了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; } };