Binary Tree Maximum Path Sum

liujs 发布于2019-08-14 17:05 / 2234人阅读

摘要：分三种情况，从中取最大左子树的右子树的跨根节点方案把节点的设为整数最小值以保证为负时至少一个值比较方案和方案左子树的和右子树的跨情况

Given a binary tree, find the maximum path sum.

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

class ResultType{
    int root2any;
    int any2any;
    ResultType(int root2any, int any2any){
        this.root2any = root2any;
        this.any2any = any2any;
    }
}

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public int maxPathSum(TreeNode root) {
        return helper(root).any2any;
    }
    //分三种情况，从中取最大： 左子树的any2any, 右子树的any2any,跨根节点方案
    public ResultType helper(TreeNode root){
        if (root == null){
            //把null节点的any2any设为整数最小值以保证root为负时至少return一个值
            return new ResultType(0,Integer.MIN_VALUE);
        }
        //divide 
        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        
        
        //conquer
        int root2any = Math.max(0, Math.max(left.root2any,right.root2any)) + root.val;
        //比较方案1和方案2（左子树的any2any和右子树的any2any）
        int any2any = Math.max(left.any2any,right.any2any);
        //跨root情况
        any2any = Math.max(any2any, Math.max(0,left.root2any) + Math.max(0,right.root2any) + root.val);
        
        return new ResultType(root2any, any2any);
    }
}

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/66417.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-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
leetcode124. Binary Tree Maximum Path Sum

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

frank_fun 2019-08-15 11:11 评论0 收藏0
[LintCode/LeetCode] Binary Tree Maximum Path Sum

摘要：调用函数更新路径和的最大值，而函数本身需要递归，返回的是单边路径和。所以函数要返回的是，主函数中返回的却是最上一层根节点处和的较大值，与之前遍历过所有路径的最大值之间的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...

cnTomato 2019-08-14 15:34 评论0 收藏0