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

我正在努力解决这个问题，我想以非递归的方式解决。我的算法似乎没有逻辑错误，通过了73％的测试用例。但是它不能处理大数据，报告“超过时间限制”。如果有人可以提示我如何以非递归方式进行操作并避免超过时间限制，我将不胜感激，在此先感谢您!

问题链接



问题描述:



示例:



返回4.(1-> 3)

法官



输入
输入数据



预期的



我的代码
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;
    }
};

最佳答案

从上至下，通过向其添加父节点的值来更新每个节点。跟踪您的最大值及其位置。最后返回。上)。

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

关于c++ - 二叉树最大路径总和，非递归，超过时间限制，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39677399/