【LeetCode热题100】【二叉树】二叉树中的最大路径和

叶茂林

发布于 2024-04-12 08:32:26

800

发布于 2024-04-12 08:32:26

天美后台开发一面第三题，之前做过543. 二叉树的直径 - 力扣（LeetCode），解法基本一样，只不过累积的值变成了权重，还是用递归，不过我面试的时候没有考虑到负数的情况，有点遗憾，希望给个机会

class Solution {
public:
    int ans = INT32_MIN;

    int depth(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int R = max(depth(root->right), 0);
        int L = max(depth(root->left), 0);
        ans = max(ans, R + L + root->val);
        return max(R, L) + root->val;
    }

    int maxPathSum(TreeNode *root) {
        depth(root);
        return ans;
    }
};

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-10，如有侵权请联系 cloudcommunity@tencent.com 删除

面试