LeetCode[124] Binary Tree Maximum Path Sum

warmcheng 發布于2019-08-16 10:27 / 2395人閱讀

摘要：復雜度思路對于每一節點，考慮到這一個節點為止，所能形成的最大值。，是經過這個節點為止的能形成的最大值的一條支路。

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 sequence of nodes from some
starting node to any node in the tree along the parent-child

The path must contain at least one node and does not need

go through the root.

For example: Given the below binary tree,

  1
 / 
2   3

Return 6.

DFS

復雜度
O(N)

思路
對于每一節點，考慮到這一個節點為止，所能形成的最大值。Math.max(left.val, right.val) + root.val，是經過這個節點為止的能形成的最大值的一條支路。

代碼

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

GPU云服務器云服務器 binary-tree binary-search-tree Maximum cdn124

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69815.html

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
[LeetCode] 124. Binary Tree Maximum Path Sum

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 co...

mdluo 2019-08-16 13:30 評論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