[LeetCode] 124. Binary Tree Maximum Path Sum

mdluo 發(fā)布于2019-08-16 13:30 / 1357人閱讀

Problem

Given a non-empty 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.

Example 1:

Input: [1,2,3]

       1
      / 
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / 
  9  20
    /  
   15   7

Output: 42

Solution

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

云服務(wù)器 GPU云服務(wù)器 binary-tree binary-search-tree Maximum cdn124

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/71865.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 2019-08-16 10:27 評論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 2019-07-30 16:06 評論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 2019-08-15 11:11 評論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 2019-08-16 10:27 評論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...

魏憲會 2019-08-14 12:25 評論0 收藏0