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.

難度：75.?

參見(jiàn)了他人的思路，這道題是求樹(shù)的路徑和的題目，不過(guò)和平常不同的是這里的路徑不僅可以從根到某一個(gè)結(jié)點(diǎn)，而且路徑可以從左子樹(shù)某一個(gè)結(jié)點(diǎn)，然后到達(dá)右子樹(shù)的結(jié)點(diǎn)，就像題目中所說(shuō)的可以起始和終結(jié)于任何結(jié)點(diǎn)。函數(shù)的返回值定義為以自己為根的一條從根到葉子結(jié)點(diǎn)的最長(zhǎng)路徑，這個(gè)返回值是為了提供給它的父結(jié)點(diǎn)計(jì)算自身的最長(zhǎng)路徑用。這樣一來(lái)，一個(gè)結(jié)點(diǎn)自身的最長(zhǎng)路徑就是它的左子樹(shù)返回值（如果大于0的話），加上右子樹(shù)的返回值（如果大于0的話），再加上自己的值。在過(guò)程中求得當(dāng)前最長(zhǎng)路徑時(shí)比較一下是不是目前最長(zhǎng)的，如果是則更新。算法的本質(zhì)還是一次樹(shù)的遍歷，所以復(fù)雜度是O(n)。而空間上仍然是棧大小O(logn)。注意這里path的存值方式是個(gè)問(wèn)題，如果用一個(gè)integer變量代入recursion的話，函數(shù)無(wú)法對(duì)實(shí)參造成改變，所以用了一個(gè)對(duì)象ArrayList<Integer> res的第一個(gè)元素來(lái)存最大的path值

1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public int maxPathSum(TreeNode root) { 12 if (root == null) return 0; 13 ArrayList<Integer> res = new ArrayList<Integer>(); 14 res.add(Integer.MIN_VALUE); 15 FindMaxSum(root, res); 16 return res.get(0); 17 } 18 19 public int FindMaxSum(TreeNode root, ArrayList<Integer> res) { 20 if (root == null) { 21 return 0; 22 } 23 int leftsum = FindMaxSum(root.left, res); 24 int rightsum = FindMaxSum(root.right, res); 25 int maxsum = root.val + (leftsum>0? leftsum : 0) + (rightsum>0? rightsum : 0); 26 if (maxsum > res.get(0)) res.set(0, maxsum); 27 return root.val + Math.max(leftsum, Math.max(rightsum, 0)); 28 } 29 }

?

總結(jié)

以上是生活随笔為你收集整理的Leetcode: Binary Tree Maximum Path Sum的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。