首页 > 试题广场 >

二叉树中的最大路径和

[编程题]二叉树中的最大路径和
  • 热度指数:73001 时间限制: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 ,节点上的值满足
要求:空间复杂度 ,时间复杂度
示例1

输入

{1,2,3}

输出

6
示例2

输入

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

输出

41

说明


其中一条最大路径为:15=>20=>6,路径和为15+20+6=41   
示例3

输入

{-2,#,-3}

输出

-2

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
class Solution {
public:
    int maxPathSum(TreeNode *root) {
    	if (root == 0) {
    		return 0;
    	}
    	queue<TreeNode*> q;
    	q.push(root);
    	int max = root->val;
    	while (!q.empty()) {
    		TreeNode *node = q.front();
    		q.pop();
    		int left = maxPathSumCore(node->left);
    		int right = maxPathSumCore(node->right);
    		int cur = node->val;
    		if (left > 0) {
    			cur += left;
    		}
    		if (right > 0) {
    			cur += right;
    		}
    		if (cur > max) {
    			max = cur;
    		}
    		if (node->left != 0) {
    			q.push(node->left);
    		}
    		if (node->right != 0) {
    			q.push(node->right);
    		}
    	}
    	return max;
    }

    int maxPathSumCore(TreeNode *node) {
    	if (node == 0) {
    		return 0;
    	}
    	int left = maxPathSumCore(node->left);
    	int right = maxPathSumCore(node->right);
    	int max = node->val;
    	int bigger = left >= right ? left : right;
    	if (bigger > 0) {
    		max += bigger;
    	}
    	return max;
    }
};
发表于 2017-09-07 13:44:09 回复(0)

这一题有点类似一维数组求最大子序列的和,一维最大子序列和从一维的角度判断,这里二叉树有左右子树考虑。
maxpath(root)方法的返回值的意思就是求得root节点到该root子孙的任意一节点的最大路径值(注意区别这里root和根节点root,这里root是递归下去的节点)。在这个函数里还比较了以root为路径节点
if (maxsum < sum)
maxsum = sum;//

int maxsum = Integer.MIN_VALUE;// 初始化为最小值

    public int maxPathSum(TreeNode root) {
        if (root == null)
            return 0;

        maxSum(root);
        return maxsum;
    }

    public int maxSum(TreeNode root) {

        if (root == null)
            return 0;
        int left = maxSum(root.left);
        int right = maxSum(root.right);
        int sum = root.val;
        if (left > 0)
            sum += left;
        if (right > 0)
            sum += right;
        if (maxsum < sum)
            maxsum = sum;
        return Math.max(left, right) > 0 ? Math.max(left, right) + root.val : root.val;
    }
发表于 2017-04-26 15:13:51 回复(1)
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
  /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
  int maxPathSum(TreeNode* root) {
    ans_ = INT_MIN;
    dfs(root);
    return ans_;
  }
  
private:
  int ans_;
  
  int dfs(TreeNode* root) {
    if (!root) return 0;
    const int ls = max(0, dfs(root->left));
    const int rs = max(0, dfs(root->right));
    ans_ = max(ans_, root->val + ls + rs);
    return root->val + max(ls, rs); 
  }
};

发表于 2021-07-19 12:43:11 回复(0)
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)
class Solution {
    int ma;
public:
    int maxPathSum(TreeNode *root) {
        ma = 0x80000000;
        int res = search(root);
        res = max(res, ma);
        return res;
        
    }
    int search(TreeNode* root) {
        if(root == NULL) {
            return 0;
        }
        int lh = search(root->left);
        int rh = search(root->right);
        int lst = max(lh, rh);
        //三种情况:1.包含一个子树和顶点,2.仅包含顶点,3.包含左子树和右子树以及顶点。
        int sum = lh + rh + root->val;//情况3
        sum = max(sum, root->val);//情况2
        sum = max(sum, lst + root->val);//情况1
        //取最大值
        if(sum > ma) {
            ma = sum;
        }
        //对于每一个子树,返回包含该子树顶点的深度方向的路径和的最大值。
        int rt = lst + root->val;
        rt = max(rt, root->val);
        return rt;
    }
};

发表于 2016-09-18 21:37:59 回复(0)
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        if(!root) return 0;
        int maxSum = --65535;//这里的初始值必须设为一个不可能达到的负数 最大值有可能为负的情况
        maxlu(root,maxSum);//递归遍历所有结点的同时时刻更新可能的最大路径值
        return maxSum;
    }
    int maxlu(TreeNode* root, int& maxSum) {
        if(!root) return 0;
        int L = maxlu(root->left,maxSum);
        int R = maxlu(root->right,maxSum);
        if(root->val>maxSum) maxSum = root->val;
        if((L+R+root->val)>maxSum) maxSum = L+R+root->val;
        int curVal =  L > R ? L + root->val : R + root->val;
        if(curVal>maxSum) maxSum = curVal;
        if(curVal > 0) return curVal; //只有大于0的分支路径是需要的否则只会降低当前最大值 
        else return 0;
    }
};
发表于 2017-11-20 11:14:19 回复(0)
    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)
class Solution {
    /**
     *  问题分解,求树的最大路径,递归树的节点
     *  有三种可能:
     *    1. 最大路径经过该节点本身从左子树到右子树
     *    2. 最大路径经过节点本身向父节点发展
     *    3. 最大路径就是节点本身
     *  可以将左右边子树返回的满足情况2的最大路径和f(left),f(right)
     *  ,以及节点本身值val, 做一个组合,假设当前最大值是MAX
     *  MAX = max(val, f(left)+val+f(right), f(left)+val, f(right)+val)
     *  因为要满足递归条件,向上级返回的f(n)只能是情况2或者3
     *  f(n) = max(val, f(left)+val, f(right)+val)
     */
    int MAX = Integer.MIN_VALUE;
    public int calculate(TreeNode node){
        if(node == null) return 0;
        int left = 0;
        int right = 0;
        if(node.left!=null) left = calculate(node.left);
        if(node.right!=null) right = calculate(node.right);
        int sum = node.val;
        if(left>0) sum += left;
        if(right>0) sum += right;
        MAX = Math.max(MAX, sum);
        return Math.max(node.val, Math.max(left+node.val, right+node.val));
    }
    public int maxPathSum(TreeNode root) {
        calculate(root);
        return MAX;            
    }
}

发表于 2020-01-08 12:13:54 回复(1)
public class Solution {

    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        process(root);
        return max;
    }


    // 每个节点返回最大值
    public int process(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftData = Math.max(0, process(root.left));
        int rightData = Math.max(0, process(root.right));
        int sum = leftData + rightData + root.val;
        max = Math.max(sum, max);
        return Math.max(leftData, rightData) + root.val;
    }
}
发表于 2019-11-06 15:57:32 回复(1)
// 对于每个节点都要考虑:  【递归】
//    1\. 自己作为 root是不是就已经全局最大了(全局参数max,一直在更新)
//    2\. 这个节点的最大单边贡献(需要累加)
import java.lang.Integer;
public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root==null)    return 0;
        run(root);
        return max;
    }

    //1\. 是不是天选之点(更新max)  2.return:单边最大贡献
    public int run(TreeNode t){
        int leftContribution = 0;
        int rightContribution = 0;
        int currentMax = t.val; //负的也得经过自己这个节点

        if(t.left!=null)     leftContribution = run(t.left);
        if(t.right!=null)    rightContribution = run(t.right);

        //算自己作为root的最大值,看是不是天选之点
        if(leftContribution>0)     currentMax = currentMax + leftContribution;
        if(rightContribution>0)    currentMax = currentMax + rightContribution;
        if(currentMax > max){
            max = currentMax;
        }

        return Math.max(t.val, Math.max(t.val+leftContribution, t.val+rightContribution));
    }
}
编辑于 2018-07-14 17:41:25 回复(1)
class Solution {
    int maxDis;
public:
    int maxPathSum(TreeNode *root) {
        if(!root){
            maxDis=0;
            return -1e8;
        }
        int lMax=maxPathSum(root->left),l=max(0,maxDis);
        int rMax=maxPathSum(root->right),r=max(0,maxDis);
        maxDis=max(l,r)+root->val;
        return max(lMax,max(rMax,l+r+root->val));
    }
};

发表于 2018-05-27 20:33:58 回复(0)
在递归函数中,如果当前结点不存在,那么直接返回0。否则就分别对其左右子节点调用递归函数,由于路径和有可能为负数,而我们当然不希望加上负的路径和,所以我们和0相比,取较大的那个,就是要么不加,加就要加正数。然后我们来更新全局最大值结果res,就是以左子结点为终点的最大path之和加上以右子结点为终点的最大path之和,还要加上当前结点值,这样就组成了一个条完整的路径。而我们返回值是取left和right中的较大值加上当前结点值,因为我们返回值的定义是以当前结点为终点的path之和,所以只能取left和right中较大的那个值,而不是两个都要
发表于 2018-04-29 10:45:17 回复(0)
public class Solution {  
    private int max = Integer.MIN_VALUE;  
      
    public int maxPathSum(TreeNode root) {  
        maxSum(root);  
        return max;  
    }  
      
    public int maxSum(TreeNode root) {
		if(root == null) return 0;
		int leftVal = maxSum(root.left);
		int rightVal = maxSum(root.right);
		int curMax = root.val;
		if(leftVal > 0) curMax += leftVal;
		if(rightVal > 0) curMax += rightVal;
		max = max > curMax ? max : curMax;
		return Math.max(root.val, Math.max(root.val + leftVal, root.val + rightVal));
	}
}  

发表于 2017-03-19 20:48:26 回复(0)
 我们递归计算通过每个节点的最大路径和 ( left + right + val), 与通过该节点的最大子路径的分支(max(left, right) + val), 每次更新一下最大路径和就可以了
发表于 2016-03-29 11:16:14 回复(0)
/*
大致思路是递归找root节点左边最大路径和右边最大路径二者最大值加上root的值,递归过程参考了一位大佬的思路,考虑求左或右边最大路径可能为负值,遇到这种情况让这个最大路径取0,这样就避免了最后求最大值时取加上那个负数
*/
class Solution {
public:
    int maxValue = -1000;  //存储暂时的最大值
    int tempMaxPathSum(TreeNode *root) {   //递归:根据root找到从左子树最大路径、右子树最大路径二者的最大值
           if(root == nullptr)
            return 0;   //
        int left = max(0,tempMaxPathSum(root->left));  //找到左子树最大路径,如果为负数则置为0
        int right = max(0,tempMaxPathSum(root->right));
        maxValue = max(maxValue,left + right + root->val);   //递归中修改maxValue的值
        return max(left,right) + root->val;  
    }
    int maxPathSum(TreeNode *root) {
        tempMaxPathSum(root);
        return maxValue;
    }
};
发表于 2017-11-23 11:25:21 回复(0)
public class Solution {
    int maxValue;
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;     
    }
    private int maxPathDown(TreeNode node){
        if(node==null)
            return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}

发表于 2016-06-16 09:36:15 回复(13)
/*
 * 124. Binary Tree Maximum Path Sum
 * 解题思路:(转载自:http://blog.csdn.net/linhuanmars/article/details/22969069)
 * 这道题是求树的路径和的题目,不过和平常不同的是这里的路径不仅可以从根到某一个结点,
 * 而且路径可以从左子树某一个结点,然后到达右子树的结点,就像题目中所说的可以起始和终结于任何结点。
 * 在这里树没有被看成有向图,而是被当成无向图来寻找路径。
 * 因为这个路径的灵活性,我们需要对递归返回值进行一些调整,而不是通常的返回要求的结果。
 * 在这里,函数的返回值定义为以自己为根的一条从根到子结点的最长路径(这里路径就不是当成无向图了,
 * 必须往单方向走)。
 * 这个返回值是为了提供给它的父结点计算自身的最长路径用,
 * 而结点自身的最长路径(也就是可以从左到右那种)则只需计算然后更新即可。
 * 这样一来,一个结点自身的最长路径就是它的左子树返回值(如果大于0的话),
 * 加上右子树的返回值(如果大于0的话),再加上自己的值。
 * 而返回值则是自己的值加上左子树返回值,
 * 右子树返回值或者0(注意这里是“或者”,而不是“加上”,因为返回值只取一支的路径和)。
 * 在过程中求得当前最长路径时比较一下是不是目前最长的,如果是则更新。
 * 算法的本质还是一次树的遍历,所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。
 */

// 因为maxPathSum不一定经过根节点,所以用maxValue整个遍历过程中出现过的最大值
	int maxValue = 0;

	public int maxPathSum(TreeNode root) {
		if (root == null)
			return 0;
		maxValue = Integer.MIN_VALUE;
		getMaxPathSum(root);
		return maxValue;
	}

	private int getMaxPathSum(TreeNode root) {
		if (root == null)
			return 0;
		//因为节点的值可以为负数,所以最大值取0和子树值的较大者
		int leftMax = Math.max(0, getMaxPathSum(root.left));
		int rightMax = Math.max(0, getMaxPathSum(root.right));
		//如果将当前root作为根节点,那么最大值是root.val+左子树最大值+右子树最大值
		maxValue = Math.max(maxValue, root.val + leftMax + rightMax);
		//只能返回左右子树中较大值加上root.val
		return Math.max(0, root.val + Math.max(leftMax, rightMax));
	}

编辑于 2017-08-09 11:20:00 回复(7)
class Solution {
public:     int Max;
    int maxPathSum(TreeNode *root) {
        Max = INT_MIN;
        maxSum(root);         return Max;
    }
    int maxSum(TreeNode *root){
        if(root == NULL)
            return 0;
        int l_Max = max(0, maxSum(root->left));
        int r_Max = max(0, maxSum(root->right));
        Max = max(Max, l_Max + r_Max + root->val);
        return max(l_Max, r_Max) + root->val;     }
};


发表于 2017-09-20 15:14:02 回复(0)
/*
题目描述:
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
       1
      / \
     2   3

Return6.

思路:

首先我们分析一下对于指定某个节点为根时,最大的路径和有可能是哪些情况:
第一种是左子树的路径加上当前节点,
第二种是右子树的路径加上当前节点,
第三种是左右子树的路径加上当前节点(相当于一条横跨当前节点的路径),
第四种是只有自己的路径。

乍一看似乎以此为条件进行自下而上递归就行了,然而这四种情况只是
用来计算以当前节点根的最大路径,如果当前节点上面还有节点,
那它的父节点是不能累加第三种情况的。所以我们要计算两个最大值,
一个是当前节点下最大路径和,另一个是如果要连接父节点时最大的路径和。
我们用前者更新全局最大量,用后者返回递归值就行了。


*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <map>

using namespace std;

// Definition for binary tree
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 
class Solution {
public:
    int maxPathSum(TreeNode *root) {
    int maxPath = 0x80000000;

    dfsPathSum(root, maxPath);
    return maxPath;    
    }

    int dfsPathSum(TreeNode *root, int &maxPath) 
    {
    if(!root) return 0;

int left, right;
left = dfsPathSum(root->left, maxPath);
right = dfsPathSum(root->right, maxPath);

int curMax = Max(Max(left + root->val, right + root->val), 
Max(root->val, root->val + left + right));
maxPath = Max(curMax, maxPath); 

return Max(root->val, root->val + Max(left, right));    
    }
    int Max(int a, int b)
    {
    if(a>b)
    return a;
    return b;
    }
};

发表于 2016-10-10 18:22:25 回复(3)
class Solution:
    def __init__(self):
        self.max_weight = -10000

    def maxPathSum(self, root: TreeNode) -> int:
        # write code here
        self.maxPath(root)
        return self.max_weight

    def maxPath(self, root):
        if root is None:
            return 0
        left_weight = self.maxPath(root.left)
        right_weight = self.maxPath(root.right)
        self.max_weight = max(
            self.max_weight,
            root.val + left_weight + right_weight,
            root.val,
            root.val + left_weight,
            root.val + right_weight,
        )
        ret = max(root.val, root.val + left_weight, root.val + right_weight)
        return ret
朋友们救救孩子,为什么这段代码自测一点问题也没有,提交死活提交不上去。显示如下:
程序异常退出,请检查是否存在语法错误或者数组越界非法访问等情况
File "/tmp/a.py3", line 14, in run
ret = solution.maxPathSum( root )
File "/tmp/solution.py", line 19, in maxPathSum
self.maxPath(root)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 26, in maxPath
right_weight = self.maxPath(root.right)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 26, in maxPath
right_weight = self.maxPath(root.right)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
.........


发表于 2022-03-09 16:11:11 回复(1)