成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode124. Binary Tree Maximum Path Sum

frank_fun / 2959人閱讀

摘要：題目要求題目要求從二叉樹中找到任意兩個節(jié)點構(gòu)成的一條路徑，該路徑上節(jié)點的和為最大。其實在這里我們通過遞歸的方法可以發(fā)現(xiàn)以下幾種場景當(dāng)前節(jié)點作為起始節(jié)點當(dāng)前節(jié)點不是起始節(jié)點首先我們以當(dāng)前節(jié)點作為根節(jié)點，找到可能構(gòu)成的最大路徑值。

題目要求 
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.

For example:
Given the below binary tree,

       1
      / 
     2   3
Return 6.

題目要求：從二叉樹中找到任意兩個節(jié)點構(gòu)成的一條路徑，該路徑上節(jié)點的和為最大。

思路與代碼

在這里和其它題目不一樣的是，并非從根節(jié)點到葉節(jié)點的一條路徑，而是從任意一個節(jié)點到任意一個節(jié)點的路徑。其實在這里我們通過遞歸的方法可以發(fā)現(xiàn)以下幾種場景：

1.當(dāng)前節(jié)點作為起始節(jié)點
2.當(dāng)前節(jié)點不是起始節(jié)點

首先我們以當(dāng)前節(jié)點作為根節(jié)點，找到可能構(gòu)成的最大路徑值。也就是

1.根節(jié)點本身（如果根節(jié)點的左右子樹的最大值均<=0）
2.根節(jié)點加上左子樹
3.根節(jié)點加上右子樹

其次，如果當(dāng)前節(jié)點不是起始或結(jié)束節(jié)點，那么當(dāng)前節(jié)點就如例題中所示的2

在遞歸中，我們需要先計算當(dāng)前節(jié)點可能生成的最大路徑值并與最大值比較，同時還要返回給父節(jié)點該節(jié)點作為根節(jié)點的最大路徑值。

代碼如下：

    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSumRec(root);
        return max;
    }
    
    public int maxPathSumRec(TreeNode root){
        if(root==null) return 0;
        int left = maxPathSumRec(root.left);
        int right = maxPathSumRec(root.right);
        max = Math.max(Math.max(max, Math.max(left+root.val, right+root.val)), left+root.val+right);
        return Math.max(left+root.val, right+root.val);
    }
    
    public static void main(String[] args){
        BinaryTreeMaximumPathSum_124 b = new BinaryTreeMaximumPathSum_124();
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        t1.left = t2;
        t1.right = t3;
        b.maxPathSum(t1);
    }


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67595.html

相關(guān)文章

  • LeetCode[124] Binary Tree Maximum Path Sum

    摘要：復(fù)雜度思路對于每一節(jié)點，考慮到這一個節(jié)點為止，所能形成的最大值。，是經(jīng)過這個節(jié)點為止的能形成的最大值的一條支路。 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 評論0 收藏0

  • leetcode-124-Binary Tree Maximum Path Sum

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

    z2xy 評論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 評論0 收藏0

  • [Leetcode-Tree]Binary Tree Maximum Path Sum

    摘要：但是本題的難點在于，使用遞歸實現(xiàn)，但是前面的第四種情況不能作為遞歸函數(shù)的返回值，所以我們需要定義兩個值，代表單邊路徑的最大值，用于遞歸用于和回路的較大值。 Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. For this problem, a path is defined as a...

    caige 評論0 收藏0

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

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

    魏憲會 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<