[Leetcode-Tree]Binary Tree Maximum Path Sum

caige 發布于2019-08-16 10:27 / 437人閱讀

摘要：但是本題的難點在于，使用遞歸實現，但是前面的第四種情況不能作為遞歸函數的返回值，所以我們需要定義兩個值，代表單邊路徑的最大值，用于遞歸用于和回路的較大值。

Binary Tree Maximum Path Sum
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.

1.解題思路

分析對于每一個根節點，可能的路徑和有：左子樹的最大路徑和+該節點val，右子樹的最大路徑和+該節點val,只取該節點val,左子樹的最大路徑和+該節點val+右子樹的最大路徑和，我們需要取四個中最大的一個即可。但是本題的難點在于，使用遞歸實現，但是前面的第四種情況不能作為遞歸函數的返回值，所以我們需要定義兩個max值，singleMax代表單邊路徑的最大值，用于遞歸；curMax用于singleMax和回路Max的較大值。

2.代碼

public class Solution {
    int max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    private int helper(TreeNode root){
        if(root==null) return 0;
        int leftsum=helper(root.left);
        int rightsum=helper(root.right);
        int singlemax=Math.max(Math.max(leftsum+root.val,rightsum+root.val),root.val);
        int curmax =Math.max(singlemax,leftsum+root.val+rightsum);
        max=Math.max(max,curmax);
        return singlemax;
    }
}

GPU云服務器云服務器 binary-tree binary-search-tree Maximum Binary

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

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

[Leetcode-Tree]Maximum / Minimum Depth of Binary T

摘要：解題思路用遞歸實現很簡單，對于每個根節點，最大深度就等于左子樹的最大深度和右子樹的最大深度的較大值。解題思路本題的注意點在于如果某個根節點有一邊的子樹為空，那么它的深度就等于另一邊不為空的子樹的深度，其他的邏輯與上一題相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...

Thanatos 2019-08-16 10:26 評論0 收藏0
[Leetcode-Tree] Path Sum I II III

摘要：解題思路利用遞歸，對于每個根節點，只要左子樹和右子樹中有一個滿足，就返回每次訪問一個節點，就將該節點的作為新的進行下一層的判斷。代碼解題思路本題的不同點是可以不從開始，不到結束。代碼當前節點開始當前節點左節點開始當前節點右節點開始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 評論0 收藏0
[Leetcode-Tree] Sum Root to Leaf Numbers

摘要：解題思路本題要求所有從根結點到葉子節點的路徑和，我們用遞歸實現。結束條件當遇到葉子節點時，直接結束，返回計算好的如果遇到空節點，則返回數值。 Sum Root to Leaf NumbersGiven a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a numbe...

BigNerdCoding 2019-08-16 10:27 評論0 收藏0
[Leetcode-Tree]Sum of Left Leaves

摘要：解題思路這個題目其實就是基于先序遍歷，用遞歸和非遞歸思想都可以。遞歸求所有左葉子節點的和，我們可以將其分解為左子樹的左葉子和右子樹的左葉子和遞歸結束條件找到左葉子節點，就可以返回該節點的。代碼非遞歸判斷是否為左葉子節點遞歸 Sum of Left LeavesFind the sum of all left leaves in a given binary tree. Example:...

ashe 2019-08-16 10:26 評論0 收藏0
LeetCode[124] Binary Tree Maximum Path Sum

摘要：復雜度思路對于每一節點，考慮到這一個節點為止，所能形成的最大值。，是經過這個節點為止的能形成的最大值的一條支路。 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 2019-08-16 10:27 評論0 收藏0