首页 > 代码库 > LeetCode 124 Binary Tree Maximum Path Sum

LeetCode 124 Binary Tree Maximum Path Sum

2024-08-01 16:55:25   217人阅读

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

Return 6.

思路：本人脑子笨，一开始想了好久都木有思路，只有一个笨办法：把所有的叶子i到叶子节点j的路径都遍历一遍。最近写回溯法用递归用的多，我突然想到了递归可以。用一个全局变量max来存储最大值,然后再求最大连续子序列和。假设我们已经知道了某个节点node的左右子树的最大路径和leftmaxsum，rightmaxsum，那么这个节点node的最大路径和为Math.max(node.val,Math.max（node.val+leftmaxsum,node.val+rightmaxsum));这个节点node的最大路径和只是为了给node的父节点准备的，并非给node自己准备的。那么给node准备用啥呢---max，        temp=root.val+leftmaxsum+rightmaxsum; max=max>temp?max:temp;  这样max就能返回当前的最大路径和。代码如下：
public class Solution {
	static int max = Integer.MIN_VALUE;

	public int maxPathSum(TreeNode root) {
		max = Integer.MIN_VALUE;
		PathSum(root);
		return max;
	}

	public int PathSum(TreeNode root) {
		if(root==null) return 0;
		int leftmaxsum=0;
		int rightmaxsum=0;
		int temp=root.val;
        if(root.left!=null){
        	leftmaxsum=Math.max(PathSum(root.left),0);
        } 
        if(root.right!=null){
        	rightmaxsum=Math.max(PathSum(root.right),0);
        }
        temp=root.val+leftmaxsum+rightmaxsum;
        max=max>temp?max:temp;
        return Math.max(root.val,Math.max(root.val+leftmaxsum, root.val+rightmaxsum));
    }
}


LeetCode 124 Binary Tree Maximum Path Sum


联系
我们