[LintCode/LeetCode] Binary Tree Maximum Path Sum

cnTomato 发布于2019-08-14 15:34 / 1391人阅读

摘要：调用函数更新路径和的最大值，而函数本身需要递归，返回的是单边路径和。所以函数要返回的是，主函数中返回的却是最上一层根节点处和的较大值，与之前遍历过所有路径的最大值之间的最大值。

Problem

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

  1
 / 
2   3

return 6.

Note

调用helper函数更新路径和的最大值res，而helper函数本身需要递归，返回的是单边路径和single。这里需要注意：对于拱形路径和arch，从左子树经过根节点绕到右子树，路径已经确定，就不能再通过根节点向上求和了；对于单边路径和single，只是左边路径和left和右边路径和right的较大值与根节点的和，再与根节点本身相比的较大值，这个值还会递归到上一层继续求和。所以helper函数要返回的是single，主函数中返回的却是最上一层（根节点处）single和arch的较大值，与之前遍历过所有路径的res最大值之间的最大值。

Solution

public class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return res;
    }
    public int helper(TreeNode root) {
        if (root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        int arch = left+right+root.val;
        int single = Math.max(Math.max(left, right)+root.val, root.val);
        res = Math.max(res, Math.max(single, arch));
        return single;
    }
}

Simplified

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

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

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

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

[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不过这道题里仍要注意两个细节。中，为时，返回长度为的空数组建立结果数组时，是包括根节点的情况，是不包含根节点的情况。而非按左右子树来进行划分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 评论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
[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
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