[LintCode/LeetCode] Binary Tree Maximum Path Sum

cnTomato 發布于2019-08-14 15:34 / 1474人閱讀

摘要：調用函數更新路徑和的最大值，而函數本身需要遞歸，返回的是單邊路徑和。所以函數要返回的是，主函數中返回的卻是最上一層根節點處和的較大值，與之前遍歷過所有路徑的最大值之間的最大值。

Problem

Given a binary tree, find the maximum path sum.

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

Example

Given the below binary tree:

  1
 / 
2   3

return 6.

Note

調用helper函數更新路徑和的最大值res，而helper函數本身需要遞歸，返回的是單邊路徑和single。這里需要注意：對于拱形路徑和arch，從左子樹經過根節點繞到右子樹，路徑已經確定，就不能再通過根節點向上求和了；對于單邊路徑和single，只是左邊路徑和left和右邊路徑和right的較大值與根節點的和，再與根節點本身相比的較大值，這個值還會遞歸到上一層繼續求和。所以helper函數要返回的是single，主函數中返回的卻是最上一層（根節點處）single和arch的較大值，與之前遍歷過所有路徑的res最大值之間的最大值。

Solution

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

Simplified

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

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

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

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

[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不過這道題里仍要注意兩個細節。中，為時，返回長度為的空數組建立結果數組時，是包括根節點的情況，是不包含根節點的情況。而非按左右子樹來進行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 評論0 收藏0
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