国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Binary Tree Maximum Path Sum

liujs / 2235人閱讀

摘要：分三種情況，從中取最大左子樹的右子樹的跨根節點方案把節點的設為整數最小值以保證為負時至少一個值比較方案和方案左子樹的和右子樹的跨情況

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);
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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 評論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 評論0 收藏0

  • [Leetcode] Binary Tree Maximum Path Sum 二叉樹最大路徑和

    摘要：棧迭代復雜度時間空間遞歸棧空間對于二叉樹思路首先我們分析一下對于指定某個節點為根時，最大的路徑和有可能是哪些情況。代碼連接父節點的最大路徑是一二四這三種情況的最大值當前節點的最大路徑是一二三四這四種情況的最大值用當前最大來更新全局最大 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum...

    魏憲會 評論0 收藏0

  • leetcode-124-Binary Tree Maximum Path Sum

    摘要：題目描述舉例題目分析找從任意節點出發的任意路徑的最大長度。每個都有可能是其他路徑上的，這種情況要，。每個都有可能作為中心，此時要左側之前的路徑最長長度，左側之前的路徑最長長度，此為中心時候的長度將這個分析單元遞歸封裝，即可實現目標。 題目描述： Given a binary tree, find the maximum path sum. For this problem, a p...

    z2xy 評論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 評論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 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<