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

資訊專欄INFORMATION COLUMN

leetcode-124-Binary Tree Maximum Path Sum

z2xy / 3294人閱讀

摘要：題目描述舉例題目分析找從任意節(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 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.


舉例：


Given the below binary tree,

   1
  / 
 2   3
Return 6.


題目分析： 找從任意節(jié)點(diǎn)出發(fā)的任意路徑的最大長(zhǎng)度。  每個(gè)node都有可能是其他路徑上的node，這種情況要max(left，right)。如此循環(huán)。  每個(gè)node都有可能作為中心node，此時(shí)要max(左側(cè)之前的路徑最長(zhǎng)長(zhǎng)度，左側(cè)之前的路徑最長(zhǎng)長(zhǎng)度，此node為中心時(shí)候的長(zhǎng)度)
將這個(gè)分析單元遞歸封裝，即可實(shí)現(xiàn)目標(biāo)。
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def dfs(self,node):
        ls = rs = None
        lmv = rmv = 0
        if node.left:
            lmv,ls=self.dfs(node.left)
            lmv=max(lmv,0)
        if node.right:
            rmv,rs=self.dfs(node.right)
            rmv=max(rmv,0)
        # print(lmv,rmv,ls,rs)
        mv=node.val+max(lmv,rmv)
        sv=node.val+lmv+rmv
        # mv=node.val
        trans_list=[elem for elem in [sv,ls,rs] if elem]
        if not trans_list:
            trans_list=[0]
        return mv,max(trans_list)

    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return
        mv,smv=self.dfs(root)
        return max(mv,smv)

if __name__=="__main__":
    tn=TreeNode(2)
    tn1=TreeNode(-1)
    tn2=TreeNode(-2)
    tn.left=tn1
    tn.right=tn2

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

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

相關(guān)文章

  • LeetCode[124] Binary Tree Maximum Path Sum

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

  • leetcode124. Binary Tree Maximum Path Sum

    摘要：題目要求題目要求從二叉樹(shù)中找到任意兩個(gè)節(jié)點(diǎn)構(gòu)成的一條路徑，該路徑上節(jié)點(diǎn)的和為最大。其實(shí)在這里我們通過(guò)遞歸的方法可以發(fā)現(xiàn)以下幾種場(chǎng)景當(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 評(píng)論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 評(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 二叉樹(shù)最大路徑和

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

    魏憲會(huì) 評(píng)論0 收藏0

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

0條評(píng)論

閱讀需要支付1元查看
<