首页 > 试题广场 >

二叉树中的最大路径和

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

热度指数：77451 时间限制：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(dfs(root.left) ,0);
    int right = Math.max(dfs(root.right) ,0);
    maxVal=Math.max(maxVal ,root.val+left+right);
    return root.val+Math.max(left ,right);
}

发表于 2024-06-16 16:14:03 回复(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)

提交观点

问题信息

树 dfs

难度：

38条回答 910收藏 28945浏览

通过挑战的用户

查看代码

普信员

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，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题