成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Binary Tree Maximum Path Sum

cnTomato / 1540人閱讀

摘要：調(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 tree.

Example

Given the below binary tree:

  1
 / 
2   3

return 6.

Note

調(diào)用helper函數(shù)更新路徑和的最大值res，而helper函數(shù)本身需要遞歸，返回的是單邊路徑和single。這里需要注意：對(duì)于拱形路徑和arch，從左子樹經(jīng)過根節(jié)點(diǎn)繞到右子樹，路徑已經(jīng)確定，就不能再通過根節(jié)點(diǎn)向上求和了；對(duì)于單邊路徑和single，只是左邊路徑和left和右邊路徑和right的較大值與根節(jié)點(diǎn)的和，再與根節(jié)點(diǎn)本身相比的較大值，這個(gè)值還會(huì)遞歸到上一層繼續(xù)求和。所以helper函數(shù)要返回的是single，主函數(shù)中返回的卻是最上一層（根節(jié)點(diǎn)處）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);
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65852.html

相關(guān)文章

  • [LintCode/LeetCode] House Robber III

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

    macg0406 評(píng)論0 收藏0

  • LeetCode[124] Binary Tree Maximum Path Sum

    摘要：復(fù)雜度思路對(duì)于每一節(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 評(píng)論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 評(píng)論0 收藏0

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

    摘要：棧迭代復(fù)雜度時(shí)間空間遞歸棧空間對(duì)于二叉樹思路首先我們分析一下對(duì)于指定某個(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ì) 評(píng)論0 收藏0

  • leetcode-124-Binary Tree Maximum Path Sum

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

    z2xy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<