<del id="aaiqc"></del>

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

魏憲會發布于2019-08-14 12:25 / 2006人閱讀

摘要：棧迭代復雜度時間空間遞歸棧空間對于二叉樹思路首先我們分析一下對于指定某個節點為根時，最大的路徑和有可能是哪些情況。代碼連接父節點的最大路徑是一二四這三種情況的最大值當前節點的最大路徑是一二三四這四種情況的最大值用當前最大來更新全局最大

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

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

For example: Given the below binary tree,

   1
  / 
 2   3

Return 6.

棧迭代 復雜度

時間 O(b^(h+1)-1) 空間 O(h) 遞歸棧空間對于二叉樹b=2

思路

首先我們分析一下對于指定某個節點為根時，最大的路徑和有可能是哪些情況。第一種是左子樹的路徑加上當前節點，第二種是右子樹的路徑加上當前節點，第三種是左右子樹的路徑加上當前節點（相當于一條橫跨當前節點的路徑），第四種是只有自己的路徑。乍一看似乎以此為條件進行自下而上遞歸就行了，然而這四種情況只是用來計算以當前節點根的最大路徑，如果當前節點上面還有節點，那它的父節點是不能累加第三種情況的。所以我們要計算兩個最大值，一個是當前節點下最大路徑和，另一個是如果要連接父節點時最大的路徑和。我們用前者更新全局最大量，用后者返回遞歸值就行了。

代碼

public class Solution {
    
    private int max = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    public int helper(TreeNode root) {
        if(root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        //連接父節點的最大路徑是一、二、四這三種情況的最大值
        int currSum = Math.max(Math.max(left + root.val, right + root.val), root.val);
        //當前節點的最大路徑是一、二、三、四這四種情況的最大值
        int currMax = Math.max(currSum, left + right + root.val);
        //用當前最大來更新全局最大
        max = Math.max(currMax, max);
        return currSum;
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree 二叉樹 python二叉樹

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

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

前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 之 JavaScript 解答第104題 —— 二叉樹的最大深度

摘要：小鹿題目二叉樹的最大深度給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。求二叉樹的深度，必然要用到遞歸來解決。分別遞歸左右子樹。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿題目：Maximum Depth of Binary Tre...

boredream 2019-08-23 17:07 評論0 收藏0
LeetCode 104 Maximum Depth of Binary Tree 二叉樹最大深度

LeetCode 104 Maximum Depth of Binary Tree難度：Easy 題目描述：找到一顆二叉樹的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...

PiscesYE 2019-08-16 13:28 評論0 收藏0