首页 / 算法 / 新手算法学习之路----二叉树（二叉树最大路径和）

新手算法学习之路----二叉树（二叉树最大路径和）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了新手算法学习之路----二叉树（二叉树最大路径和），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1086字，纯文字阅读大概需要2分钟。

内容图文

摘抄自：https://segmentfault.com/a/1190000003554858#articleHeader2

题目：

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.

思路：首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。第一种是左子树的路径加上当前节点，第二种是右子树的路径加上当前节点，第三种是左右子树的路径加上当前节点（相当于一条横跨当前节点的路径），第四种是只有自己的路径。乍一看似乎以此为条件进行自下而上递归就行了，然而这四种情况只是用来计算以当前节点根的最大路径，如果当前节点上面还有节点，那它的父节点是不能累加第三种情况的。所以我们要计算两个最大值，一个是当前节点下最大路径和，另一个是如果要连接父节点时最大的路径和。我们用前者更新全局最大量，用后者返回递归值就行了。

Java代码：

            public
            class
             Solution {
    
    
            private
            int max = Integer.MIN_VALUE;
    
    publicint maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    publicint helper(TreeNode root) {
        if(root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        //连接父节点的最大路径是一、二、四这三种情况的最大值int currSum = Math.max(Math.max(left + root.val, right + root.val), root.val);
        //当前节点的最大路径是一、二、三、四这四种情况的最大值int currMax = Math.max(currSum, left + right + root.val);
        //用当前最大来更新全局最大
        max = Math.max(currMax, max);
        return currSum;
    }
}

 

原文：http://www.cnblogs.com/junliu37/p/7224172.html

内容总结

以上是互联网集市为您收集整理的新手算法学习之路----二叉树（二叉树最大路径和）全部内容，希望文章能够帮你解决新手算法学习之路----二叉树（二叉树最大路径和）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

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

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

来源：【匿名】