二叉树最大路径和，非递归，超过时间限制

Question

我正在努力解决这个问题，我想以非递归的方式解决这个问题。我的算法似乎没有逻辑错误，73% 的测试用例通过了。但它无法处理大数据，报告 "Time Limit Exceeded"。如果有人能给我一些提示，如何以非递归方式执行此操作并避免超过时间限制，我将不胜感激，在此先感谢！

问题Link

I believe there's also a similar one in LeetCode.

http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/

问题描述：

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.

示例：

Given the below binary tree:

1

/ \

2 3

return 4. (1->3)

法官

Time Limit Exceeded

Total Runtime: 1030 ms

输入输入数据

{-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 ...

预期

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

Answer 1

已编辑：

您不需要 findPathMaxSum 函数。我还更改了 parent 映射。现在它存储 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);
            }
        }
    };

旧：

您想在 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)的解决方案。

Answer 2

从上到下，通过添加父节点的值来更新每个节点。跟踪您的最大值及其位置。 Return 最后。 O(n).

例如，如果您的二叉树是 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。

Answer 3

我猜你的代码的问题在于，当你遍历你的树时，你在每个节点中迭代以计算最大路径。最终复杂度为 O(n^2)。您需要计算流上的最大路径（在遍历树时）。

在下面的解决方案中，我使用了 here 中的 post 阶迭代算法。请原谅我用这个代替你的。

解决方法（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;
    }
}

二叉树最大路径和，非递归，超过时间限制

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

c++

algorithm

binary-tree

non-recursive