首页 > 试题广场 >

二叉树中的最大路径和

[编程题]二叉树中的最大路径和

热度指数：73629 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。

注意:

1.同一个节点在一条二叉树路径里中最多出现一次

2.一条路径至少包含一个节点，且不一定经过根节点

给定一个二叉树的根节点root，请你计算它的最大路径和

例如：
给出以下的二叉树，

最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6

数据范围：节点数满足 $1 \le n \le 10^5$ ，节点上的值满足 $|val| \le 1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3}

输出

示例2

输入

{-20,8,20,#,#,15,6}

输出

说明


其中一条最大路径为:15=>20=>6，路径和为15+20+6=41

示例3

输入

{-2,#,-3}

输出

-2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

牛客839384289号

int maxVal=Integer.MIN_VALUE;

public int maxPathSum (TreeNode root) {
    // write code here
    dfs(root);
    return maxVal;
}

public int dfs(TreeNode root){
    if(root==null){
        return 0;
    }
    int left=Math.max(0,dfs(root.left));
    int right=Math.max(0,dfs(root.right));
    maxVal=Math.max(maxVal,root.val+left+right);
    return root.val+Math.max(left,right);
}

发表于 2023-05-20 15:26:20 回复(0)

Java

MorpheusNeo

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {

    private int maxPath = 0;
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxPathSum (TreeNode root) {
        this.maxPath = Integer.MIN_VALUE;
        dfs(root);
        return this.maxPath;
    }

    public int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftMax = Math.max(0, dfs(node.left));
        int rightMax = Math.max(0, dfs(node.right));
        this.maxPath = Math.max(this.maxPath, (leftMax + rightMax + node.val));
        return Math.max(leftMax, rightMax) + node.val;
    }
}

发表于 2023-05-08 11:54:51 回复(0)

Java

万里归途

import java.util.*;

/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/

public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
int res=Integer.MIN_VALUE;
public int maxPathSum (TreeNode root) {
// write code here
oneSideMax(root);//计算单边最大路径和的同时计算最大路径和
return res;
}
public int oneSideMax(TreeNode root){
if(root==null) return 0;
//注意单边最大路径和可能为负
int left=Math.max(0,oneSideMax(root.left));
int right=Math.max(0,oneSideMax(root.right));
int sumcount=left+right+root.val;
//更新最大路径和
res=Math.max(res,sumcount);
//根据函数定义，返回以root为根的单边最大路径和,
return Math.max(left,right)+root.val;

}
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int res=Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        // write code here
        oneSideMax(root);//计算单边最大路径和的同时计算最大路径和
        return res;
    }
    public int oneSideMax(TreeNode root){
         if(root==null) return 0;
         //注意单边最大路径和可能为负
         int left=Math.max(0,oneSideMax(root.left));
        int right=Math.max(0,oneSideMax(root.right));
        int sumcount=left+right+root.val;
        //更新最大路径和
        res=Math.max(res,sumcount);
        //根据函数定义，返回以root为根的单边最大路径和,
        return Math.max(left,right)+root.val; 
        
    }
}

发表于 2022-01-29 10:44:44 回复(0)

Java

只要三星剑姬

家人们树型DP永远的神
 public static class RN {
        int pathMax;
        int resMax;

        public RN(int pathMax, int resMax) {
            this.pathMax = pathMax;
            this.resMax = resMax;
        }
    }

    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxPathSum (TreeNode root) {
        RN res = res(root);
        return Math.max(res.resMax,res.pathMax);
    }

    public static RN res(TreeNode root) {
        if (root == null) {
            return null;
        }
        RN leftRes = res(root.left);
        RN rightRes = res(root.right);
        if (leftRes != null && rightRes != null) {
            int pathMax = Math.max(Math.max(leftRes.pathMax + root.val, rightRes.pathMax + root.val),root.val);
            int max = Math.max(leftRes.resMax, rightRes.resMax);
            int resMax = Math.max(Math.max(leftRes.pathMax + root.val + rightRes.pathMax, max),root.val);
            return new RN(pathMax, resMax);
        } else if (leftRes == null && rightRes != null) {
            int pathMax =Math.max(rightRes.pathMax + root.val,root.val) ;
            int max = Math.max(root.val, rightRes.resMax);
            int resMax = Math.max(root.val + rightRes.pathMax, max);
            return new RN(pathMax, resMax);
        } else if (rightRes == null &&leftRes != null ) {
            int pathMax =Math.max(leftRes.pathMax + root.val,root.val);
            int max = Math.max(root.val, leftRes.resMax);
            int resMax = Math.max(leftRes.pathMax + root.val, max);
            return new RN(pathMax, resMax);
        } else {
            return new RN(root.val, root.val);
        }
    }

发表于 2022-01-13 17:14:34 回复(0)

Java

201812021028954

本题在做之前要做过一题，寻找最大连续子数组和，这道题就更容易解决。

本题和那道题的不同点在于，上题目是个数组，单方向遍历和判断即可，其实就是相当于树退化成了链表的样子。

而上题的思想精髓在于，前面找出的最大子数组和如果是正数就可以添加上本次数字，否则取本次数字作为和。

所以我们要考虑的是如果遍历树可以构成这样的方向去添加，研究发现，后序遍历非常符合我们想要的遍历和判断逻辑顺序！

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int max;
    public int maxPathSum (TreeNode root) {
        max = root.val;
        fun(root);
        return max;
    }
    
    public int fun(TreeNode root){
        if(root==null)return -10000;
        int left = fun(root.left);
        int right = fun(root.right);
        if(left<0){
            max = Math.max(max,Math.max(root.val, root.val+right));
            return Math.max(root.val, right+root.val);
        }
        else{
            int temp = (left+root.val);
            if(temp<0){
                max=Math.max(max,Math.max(left,right));
                return Math.max(left,right)+root.val;
            }else{
                max=Math.max(max,Math.max(temp+right,temp));
                return Math.max(temp,root.val+right);
            }
        }
    }
}

发表于 2022-01-02 11:54:21 回复(0)

Java

玄鉴

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
    dfs(root);
    return res;
    }
    public int dfs(TreeNode root){
        if(root==null) return 0;
        int v1=Math.max(0,dfs(root.left));
        int v2=Math.max(0,dfs(root.right));
        res=Math.max(res,v1+v2+root.val);
        return Math.max(v1,v2)+root.val;
    }
}

发表于 2021-12-25 22:19:50 回复(0)

Java

QinGL_ZYW

public int max = Integer.MIN_VALUE;

public int maxPathSum (TreeNode root) {
    recu(root);
    return max;
}

public int recu(TreeNode node){
    if(node == null) return 0;
    int l = Math.max(recu(node.left),0);
    int r = Math.max(recu(node.right),0);
    int max1 = Math.max(l,r);
    int max2 = l + r + node.val;
    max = Math.max(max,max2);
    return max1 + node.val;
}

发表于 2021-10-08 17:11:23 回复(0)

Java

An前码后

public class Solution {
    private int max = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        dfs(root,0);
        return max;
    }
    
    private int dfs(TreeNode node,int idx){
        if(node==null) return idx;
        int left = Math.max(0,dfs(node.left,idx));
        int right = Math.max(0,dfs(node.right,idx));
        max = Math.max(max,left+right+node.val);
        return Math.max(left,right)+node.val;
    }
}

发表于 2021-09-13 14:15:49 回复(0)

Java

谁是谁的眼

public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
int res = Integer.MIN_VALUE;
public int maxPathSum (TreeNode root) {
// write code here
hepler(root);
return res;
}
public int hepler(TreeNode root){
if(root == null){
return 0;
}
//左子树最大路径和
int leftMax = Math.max(0,hepler(root.left));
//右子树最大路径和
int rightMax = Math.max(0,hepler(root.right));

//比较单棵树的路径和、横跨左右子树路径和的大小，取得最大值
res = Math.max(res,Math.max(root.val+Math.max(leftMax,rightMax),root.val+leftMax+rightMax));

//计算单棵树的路径和
return Math.max(leftMax,rightMax)+root.val;
}
}

发表于 2021-08-22 21:17:44 回复(0)

Java

可爱的猪

import java.util.*;
//菜鸡解法：dfs，我太难了

public class Solution {
    public int maxPathSum (TreeNode root) {
        //从根节点root向下的最大路径和
        if(root==null) return 0;
        int lAns = solute(root.left);
        int rAns = solute(root.right);
        
        return Math.max(
            Math.max(
                Math.max(root.val, root.val+Math.max(lAns, rAns)), 
                root.val + lAns + rAns
            ), 
            Math.max(
                root.left==null? Integer.MIN_VALUE: maxPathSum(root.left), 
                root.right==null? Integer.MIN_VALUE: maxPathSum(root.right)
            )
        );
    }
    
    //由root节点向下的最大路径和
    public int solute(TreeNode root) {
        if(root==null) return 0;
        
        int lAns = solute(root.left);
        int rAns = solute(root.right);
        //0表示该路径不必以叶子节点结束
      return Math.max(0, Math.max(root.val, root.val+Math.max(lAns, rAns)));
    }
}

编辑于 2021-07-16 11:30:40 回复(0)

Java

又笨又懒不想上课

    int res = -1008611;
    public int maxPathSum (TreeNode root) {
        // write code here
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root) {
        if(root == null) return 0;
        //计算该节点左右子树的大小，大于0的为正收益，小于0的就不要了
        int left = Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);
        //算上根节点的收益
        int sum = left + right + root.val;
        //更新结果
        res = Math.max(res, sum);
        //返回最大收益
        return root.val + Math.max(left, right);
    }

发表于 2021-06-15 10:58:42 回复(0)

Java

惠灵顿靖

想法的基础就是dfs，深度遍历，根据题意我们要想清楚两件事情
1.节点可能是非负的，因词开始dfs的节点不一定是根节点，结束的节点也不一定是叶子结点
2.题目没有说一定要按照自顶向下的顺序遍历，也就是说还有一种情况是这样 root.left->root->root.right。这就需要我们找到左子树最大值，右子树最大值加上根。这样一个值。
最后就是比较这两种情况哪个更大，也就是代码中标记的1这一行。

*2这一行如果大家没有深入理解的话可能也会有一些疑惑，为什么返回的是Math.max(leftMax,rightMax) + root.val，而不是root.val+leftMax+rightMax。这个其实也需要大家好好的思考一下，我们这个函数getMax()的作用，只是找到root节点下的最大节点和！这点一定要搞清楚。不要被这一行代码1迷惑住，这只是我们更新res的代码。2是dfs找最大值的方式，1适用于这道题。

import java.util.*;
public class Solution {
    int maxValue;
    public int maxPathSum(TreeNode root) {
        maxValue=Integer.MIN_VALUE;
        getMax(root);
        return maxValue;
    }
    private int getMax(TreeNode node){
        if(node==null)return 0;
        int leftmax=Math.max(0,getMax(node.left));
        int rightmax=Math.max(0,getMax(node.right));
        maxValue=Math.max(Math.max((node.val+Math.max(leftmax,rightmax)),(node.val+leftmax+rightmax)),maxValue);
        return node.val+Math.max(leftmax,rightmax);
    }
}

编辑于 2021-04-17 12:20:33 回复(0)

Java

-SoFar°

int maxSum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }
    //记住一句话：每次选一条路 因此res每次更新左右子树贡献大的那条路，
    // 但我们要计算的最大子树和根据其定义：父到子即可 即当且仅当 当前节点可以分两叉 即可以算根+左+右的值 然后更新它
    //正常的返回的dfs都是只返回一条路径的值的 但是每次dfs都更新这个值罢了
    private int dfs(TreeNode root) {
        if (root==null) return 0;
        int leftValue = dfs(root.left);
        int righttValue = dfs(root.right);
        //当且仅当当前节点可以分两叉依照定义计算下子树和 左+右+根
        maxSum = Math.max(maxSum,root.val+leftValue+righttValue);
        //正常返回的dfs还是只能单条路径返回
        int res = Math.max(leftValue,righttValue)+root.val;
        return res<0?0:res;
    }

发表于 2021-03-16 23:15:26 回复(0)

Java

find_one

    private int maxMulti(int ...nums){
        int tmp=nums[0];
        for(int i=1;i<nums.length;i++){
            tmp=Math.max(tmp,nums[i]);
        }
        return tmp;
    }
    
    
    public int getMustContainRoot(TreeNode root){
        
        if(root==null){
            return -99999999;
        }
        int leftTreeMax=getMustContainRoot(root.left);
        int rightTreeMax=getMustContainRoot(root.right);
        
        return maxMulti(leftTreeMax+root.val,rightTreeMax+root.val,root.val);
        
    }
    
    public int maxPathSum (TreeNode root) {
        // write code here
        if(root==null){
            return -99999999;
        }
        int val=root.val;
        int leftMax=maxPathSum(root.left);
        int rightMax=maxPathSum(root.right);
        int leftOneWay=getMustContainRoot(root.left);
        int rightOneWay=getMustContainRoot(root.right);
       return maxMulti(val,leftMax,rightMax,leftOneWay+val,val+rightOneWay,leftOneWay+val+rightOneWay);
      
         
    }

发表于 2021-02-28 21:05:33 回复(0)

Java

牛客915296776号

public class Solution {
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return res;
    }
    
    private int res = Integer.MIN_VALUE;
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        
        int value = root.val;
        int leftValue = dfs(root.left);
        value = Math.max(value, value + leftValue);
        int rightValue = dfs(root.right);
        value = Math.max(value, value + rightValue);
        res = Math.max(res, value);
        
        return Math.max(root.val, root.val + Math.max(leftValue, rightValue));
    }
}

发表于 2020-12-24 17:30:39 回复(0)

Java

六娃lw

从leetcode学习了一波再回来的，牛客社区还是不够强大啊，热题都没什么讲解。

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxPathSum (TreeNode root) {
        // write code here
        if(root == null){return 0;}
        int[] res = {0x80000000};
        subTreeMax(root, res);
        return res[0];
    }
    
    private int subTreeMax(TreeNode root, int[] res){
        // subTreeMax()函数 1.计算包含子树根节点root的最大非折返路径和。
        // 所谓非折返，就是路径不能同时包含左右子树。折返路径就是左子树+root+右子树
        // 2. 根据最大折返路径与最大非折返路径更新最大路径和。
        if(root == null){return 0;}
        int leftMax = subTreeMax(root.left, res);
        int rightMax = subTreeMax(root.right, res);
        int childMax = Math.max(leftMax, rightMax);
        int ret = childMax > 0? childMax + root.val: root.val;
        int leftRootRight = leftMax + root.val + rightMax;
        res[0] = Math.max(res[0], Math.max(leftRootRight, ret));
        return ret;
    }
}

编辑于 2020-11-15 16:56:05 回复(0)

Java

花落梦里

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxValue=Integer.MIN_VALUE;//因为最大的路径不一定经过根，因此需要用一个全局变量来记录遍历过程中出现过的最大值
    //当只有负节点的时候，最终的最大路径和可能是负值（大于0），因此为了更新maxValue,初始将它设为最小的值。
    public int maxPathSum (TreeNode root) {
      maxPath(root);
      return maxValue;
    }
    public int maxPath(TreeNode root){
        if(root==null) return 0;
        int left=Math.max(0,maxPath(root.left));
        int right=Math.max(0,maxPath(root.right)); 
        //求root和左右节点所能组成的最大的value值
        maxValue=Math.max(maxValue,right+root.val+left);//更新最大值
        return Math.max(left,right)+root.val;//返回的时候只能选择其中一个子节点（要形成路径）
    }
 
}

发表于 2020-11-08 16:52:10 回复(0)

Java

LiberHome

class Solution {
    int maxSum = Integer.MIN_VALUE;//-2147483648
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归计算左右子节点的最大贡献值只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;
        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);
        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}

发表于 2020-07-17 18:54:40 回复(2)

提交观点

问题信息

树 dfs

难度：

37条回答 876收藏 28271浏览

通过挑战的用户

查看代码

普信员

2023-02-25 12:33:59
One Peach

2023-02-03 14:57:43
牛客30382...

2022-12-24 15:37:46
Spectre_

2022-10-29 16:58:20
牛客25234...

2022-10-21 10:33:18

二叉树中的最大路径和

输入

输出

输入

输出

说明

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题