leetcode-124. 二叉树中的最大路径和(树形dp)

全栈程序员站长

发布于 2022-09-22 10:08:15

3860

径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

示例 1：


输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：


输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 104] -1000 <= Node.val <= 1000

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution { 
   
public:
    const int INF = 0x3f3f3f3f;
    int res = -INF;
    int dp(TreeNode *root){ 
   
        if(root->left == NULL && root->right == NULL){ 
   
            res = max(res,root->val);
            return root->val;
        }
        int l = 0,r = 0;
        if(root->left)l = max(l,dp(root->left));
        if(root->right)r = max(r,dp(root->right));
        res = max(res,l + r + root->val);
        return max(l,r) + root->val;
    }
    int maxPathSum(TreeNode* root) { 
   
        dp(root);
        return res;
    }
};

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168676.html原文链接：https://javaforall.cn

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

如有侵权请联系 cloudcommunity@tencent.com 删除

https