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

魏憲會發(fā)布于2019-08-14 12:25 / 2000人閱讀

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

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.

棧迭代 復(fù)雜度

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

思路

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

代碼

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);
        //連接父節(jié)點的最大路徑是一、二、四這三種情況的最大值
        int currSum = Math.max(Math.max(left + root.val, right + root.val), root.val);
        //當(dāng)前節(jié)點的最大路徑是一、二、三、四這四種情況的最大值
        int currMax = Math.max(currSum, left + right + root.val);
        //用當(dāng)前最大來更新全局最大
        max = Math.max(currMax, max);
        return currSum;
    }
}