Binary Tree Maximum Path Sum, non-recursive, Time Limit Exceeded

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;
    }
};

Solution

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.