leetcode124. Binary Tree Maximum Path Sum

frank_fun 发布于2019-08-15 11:11 / 2800人阅读

摘要：题目要求题目要求从二叉树中找到任意两个节点构成的一条路径，该路径上节点的和为最大。其实在这里我们通过递归的方法可以发现以下几种场景当前节点作为起始节点当前节点不是起始节点首先我们以当前节点作为根节点，找到可能构成的最大路径值。

题目要求

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       1
      / 
     2   3
Return 6.

题目要求：从二叉树中找到任意两个节点构成的一条路径，该路径上节点的和为最大。

思路与代码

在这里和其它题目不一样的是，并非从根节点到叶节点的一条路径，而是从任意一个节点到任意一个节点的路径。其实在这里我们通过递归的方法可以发现以下几种场景：

1.当前节点作为起始节点
2.当前节点不是起始节点

首先我们以当前节点作为根节点，找到可能构成的最大路径值。也就是

1.根节点本身（如果根节点的左右子树的最大值均<=0）
2.根节点加上左子树
3.根节点加上右子树

其次，如果当前节点不是起始或结束节点，那么当前节点就如例题中所示的2

在递归中，我们需要先计算当前节点可能生成的最大路径值并与最大值比较，同时还要返回给父节点该节点作为根节点的最大路径值。

代码如下：

    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSumRec(root);
        return max;
    }
    
    public int maxPathSumRec(TreeNode root){
        if(root==null) return 0;
        int left = maxPathSumRec(root.left);
        int right = maxPathSumRec(root.right);
        max = Math.max(Math.max(max, Math.max(left+root.val, right+root.val)), left+root.val+right);
        return Math.max(left+root.val, right+root.val);
    }
    
    public static void main(String[] args){
        BinaryTreeMaximumPathSum_124 b = new BinaryTreeMaximumPathSum_124();
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        t1.left = t2;
        t1.right = t3;
        b.maxPathSum(t1);
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

专线服务混合云 binary-tree binary-search-tree Maximum cdn124

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67595.html

LeetCode[124] Binary Tree Maximum Path Sum

摘要：复杂度思路对于每一节点，考虑到这一个节点为止，所能形成的最大值。，是经过这个节点为止的能形成的最大值的一条支路。 Leetcode[124] Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. For this problem, a path is defined as any se...

warmcheng 2019-08-16 10:27 评论0 收藏0
leetcode-124-Binary Tree Maximum Path Sum

摘要：题目描述举例题目分析找从任意节点出发的任意路径的最大长度。每个都有可能是其他路径上的，这种情况要，。每个都有可能作为中心，此时要左侧之前的路径最长长度，左侧之前的路径最长长度，此为中心时候的长度将这个分析单元递归封装，即可实现目标。题目描述： Given a binary tree, find the maximum path sum. For this problem, a p...

z2xy 2019-07-30 16:06 评论0 收藏0
[LeetCode] 124. Binary Tree Maximum Path Sum

Problem Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child co...

mdluo 2019-08-16 13:30 评论0 收藏0
[Leetcode-Tree]Binary Tree Maximum Path Sum

摘要：但是本题的难点在于，使用递归实现，但是前面的第四种情况不能作为递归函数的返回值，所以我们需要定义两个值，代表单边路径的最大值，用于递归用于和回路的较大值。 Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. For this problem, a path is defined as a...

caige 2019-08-16 10:27 评论0 收藏0
[Leetcode] Binary Tree Maximum Path Sum 二叉树最大路径和

摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。代码连接父节点的最大路径是一二四这三种情况的最大值当前节点的最大路径是一二三四这四种情况的最大值用当前最大来更新全局最大 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum...

魏宪会 2019-08-14 12:25 评论0 收藏0