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

資訊專欄INFORMATION COLUMN

Binary Tree Maximum Path Sum

rollback / 1380人閱讀

Binary Tree Maximum Path Sum

題目鏈接:https://leetcode.com/problems...

dfs對每個(gè)node,查一下包含這個(gè)node的最大路徑值。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return globalMax;
    }
    
    int globalMax = Integer.MIN_VALUE;
    private int dfs(TreeNode root) {
        // base case
        if(root == null) return 0;
        
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        
        globalMax = Math.max(globalMax, left + right + root.val);
        
        return Math.max(left, right) + root.val;
    }
}

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66581.html

相關(guān)文章

  • LeetCode[124] Binary Tree Maximum Path Sum

    摘要:復(fù)雜度思路對于每一節(jié)點(diǎn),考慮到這一個(gè)節(jié)點(diǎn)為止,所能形成的最大值。,是經(jīng)過這個(gè)節(jié)點(diǎn)為止的能形成的最大值的一條支路。 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

    摘要:但是本題的難點(diǎn)在于,使用遞歸實(shí)現(xiàn),但是前面的第四種情況不能作為遞歸函數(shù)的返回值,所以我們需要定義兩個(gè)值,代表單邊路徑的最大值,用于遞歸用于和回路的較大值。 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 二叉樹最大路徑和

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

    魏憲會(huì) 評論0 收藏0
  • leetcode-124-Binary Tree Maximum Path Sum

    摘要:題目描述舉例題目分析找從任意節(jié)點(diǎn)出發(fā)的任意路徑的最大長度。每個(gè)都有可能是其他路徑上的,這種情況要,。每個(gè)都有可能作為中心,此時(shí)要左側(cè)之前的路徑最長長度,左側(cè)之前的路徑最長長度,此為中心時(shí)候的長度將這個(gè)分析單元遞歸封裝,即可實(shí)現(xiàn)目標(biāo)。 題目描述: Given a binary tree, find the maximum path sum. For this problem, a p...

    z2xy 評論0 收藏0
  • leetcode124. Binary Tree Maximum Path Sum

    摘要:題目要求題目要求從二叉樹中找到任意兩個(gè)節(jié)點(diǎn)構(gòu)成的一條路徑,該路徑上節(jié)點(diǎn)的和為最大。其實(shí)在這里我們通過遞歸的方法可以發(fā)現(xiàn)以下幾種場景當(dāng)前節(jié)點(diǎn)作為起始節(jié)點(diǎn)當(dāng)前節(jié)點(diǎn)不是起始節(jié)點(diǎn)首先我們以當(dāng)前節(jié)點(diǎn)作為根節(jié)點(diǎn),找到可能構(gòu)成的最大路徑值。 題目要求 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

    摘要:調(diào)用函數(shù)更新路徑和的最大值,而函數(shù)本身需要遞歸,返回的是單邊路徑和。所以函數(shù)要返回的是,主函數(shù)中返回的卻是最上一層根節(jié)點(diǎn)處和的較大值,與之前遍歷過所有路徑的最大值之間的最大值。 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

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<