[Leetcode-Tree]Binary Tree Maximum Path Sum

caige 发布于2019-08-16 10:27 / 301人阅读

摘要：但是本题的难点在于，使用递归实现，但是前面的第四种情况不能作为递归函数的返回值，所以我们需要定义两个值，代表单边路径的最大值，用于递归用于和回路的较大值。

Binary Tree Maximum Path Sum
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.解题思路

分析对于每一个根节点，可能的路径和有：左子树的最大路径和+该节点val，右子树的最大路径和+该节点val,只取该节点val,左子树的最大路径和+该节点val+右子树的最大路径和，我们需要取四个中最大的一个即可。但是本题的难点在于，使用递归实现，但是前面的第四种情况不能作为递归函数的返回值，所以我们需要定义两个max值，singleMax代表单边路径的最大值，用于递归；curMax用于singleMax和回路Max的较大值。

2.代码

public class Solution {
    int max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    private int helper(TreeNode root){
        if(root==null) return 0;
        int leftsum=helper(root.left);
        int rightsum=helper(root.right);
        int singlemax=Math.max(Math.max(leftsum+root.val,rightsum+root.val),root.val);
        int curmax =Math.max(singlemax,leftsum+root.val+rightsum);
        max=Math.max(max,curmax);
        return singlemax;
    }
}

云服务器 GPU云服务器 binary-tree binary-search-tree Maximum Binary

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

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

[Leetcode-Tree]Maximum / Minimum Depth of Binary T

摘要：解题思路用递归实现很简单，对于每个根节点，最大深度就等于左子树的最大深度和右子树的最大深度的较大值。解题思路本题的注意点在于如果某个根节点有一边的子树为空，那么它的深度就等于另一边不为空的子树的深度，其他的逻辑与上一题相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...

Thanatos 2019-08-16 10:26 评论0 收藏0
[Leetcode-Tree] Path Sum I II III

摘要：解题思路利用递归，对于每个根节点，只要左子树和右子树中有一个满足，就返回每次访问一个节点，就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始，不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 评论0 收藏0
[Leetcode-Tree] Sum Root to Leaf Numbers

摘要：解题思路本题要求所有从根结点到叶子节点的路径和，我们用递归实现。结束条件当遇到叶子节点时，直接结束，返回计算好的如果遇到空节点，则返回数值。 Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a numbe...

BigNerdCoding 2019-08-16 10:27 评论0 收藏0
[Leetcode-Tree]Sum of Left Leaves

摘要：解题思路这个题目其实就是基于先序遍历，用递归和非递归思想都可以。递归求所有左叶子节点的和，我们可以将其分解为左子树的左叶子和右子树的左叶子和递归结束条件找到左叶子节点，就可以返回该节点的。代码非递归判断是否为左叶子节点递归 Sum of Left LeavesFind the sum of all left leaves in a given binary tree. Example:...

ashe 2019-08-16 10:26 评论0 收藏0
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