首页 / JAVA / [Leetcode][JAVA] Binary Tree Maximum Path Sum

[Leetcode][JAVA] Binary Tree Maximum Path Sum

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[Leetcode][JAVA] Binary Tree Maximum Path Sum，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含834字，纯文字阅读大概需要2分钟。

内容图文

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.

 


对于树，我们可以找到其左右子树中终止于根节点的最大路径值，称为最大半路径值，如果都是正数，则可以把它们以及根节点值相加，如果其中有负数，则舍弃那一边的值（即置为零）。如此可以找到包含根节点的最大路径值。然后选择左右子树的最大半路径值中大的那个（负数则置为0）加上根节点的值作为新的最大半路径值传给父节点。

于是我们可以递归地考察每个子树，不断更新一个全局变量max。

基本情况为：子树为null,此时最大路径值应为0.

代码如下： 

             1
            int
             max;

             2
            public
            int
             maxPathSum(TreeNode root) {

             3         max = root==null?0:root.val;
 4        findMax(root);
 5return max;
 6    }
 7publicint findMax(TreeNode root) {
 8if(root==null)
 9return 0;
10int left = Math.max(findMax(root.left),0);
11int right = Math.max(findMax(root.right),0);
12         max = Math.max(max, left+right+root.val);
13return Math.max(left, right) + root.val;
14     }

 

 

原文：http://www.cnblogs.com/splash/p/4107259.html

内容总结

以上是互联网集市为您收集整理的[Leetcode][JAVA] Binary Tree Maximum Path Sum全部内容，希望文章能够帮你解决[Leetcode][JAVA] Binary Tree Maximum Path Sum所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1265409.html

来源：【匿名】