🍃 124.二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

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

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

思路

基本思想

为了得到最大的路径和,每一个节点都需要形成最大的路径和,最大的路径和可能出现在遍历的过程中,也就是最大路径不一定包含根节点,这里利用了贪心的思想

对于当前节点来说,如果最大路径包含当前节点,分为两种情况:

1. 以当前节点为节点向两边出发形成一条最长路径

   此时当前节点可以加上左右两边的节点的最长路径和

2. 当前节点和上层节点在一起形成一条最长路径

   此时当前节点向上返回时只能挑选较大的一侧返回

路径是一条线,不能出现在一个节点有两个分叉的情况,所以当前节点在向上返回时只能返回左右节点加上当前节点中的一条较大路径,只是在返回的途中由于当前节点将左右节点连接在一起形成了最大路径,从而临时的判断是不是出现了最大路径,返回时还是只能返回一侧

总结起来就是在向上返回较大的一侧时,临时判断当前节点+左右两侧的值是不是形成了最大的路径和

执行流程

1. 前序遍历正常执行
2. 判断左右两侧的和与0谁大就保留谁,防止出现返回负数的情况,负数对最大路径和无法起到增益效果
3. 临时判断当前节点+左右两侧节点是不是形成了最大路径和
4. 正常向上返回一侧节点,与上层节点拼接在一起形成路径
5. 遍历完成之后,全局变量res保存了最大路径和

代码

根据以上分析,得出以下代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    //对于每一个节点来说,都有一个当前的最大路径和
    //并且对于一个节点来说,向上返回时,只能返回左右一边,不然不能形成路径
    int res=INT_MIN;
    int maxPathSum(TreeNode* root) {
        help(root);
        return res;

    }
    int help(TreeNode* root){
        if(root==nullptr)
            return 0;
        //对于当前节点来说,当前节点的最大值是左右两边的最大值+当前值
        //返回时只能挑选左右两边较大的返回才能和上层拼接在一起形成一条路径
        int left=max(0,help(root->left));
        int right=max(0,help(root->right));
        //临时判断当前节点加上左右子树是不是形成了最大路径和
        res=max(res,left+right+root->val);
        //正常返回
        return max(left,right)+root->val;
    }
};

总结

正常向上层返回一侧数据,防止路径出现分叉,返回的途中临时判断当前节点+左右两侧节点是不是形成了最大路径和,每个节点返回之前都临时判断一下,遍历结束之后,全局变量保存了最大路径和