LC124. 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.
此题的特殊之处在于一般而言都是计算root到leaf的sum，或者中间某部分的sum，这题是只要任意联通的一条线路就可以了。求最大值的话，利用一个全局变量每次比较或者将变量存成array进行地址的传递。利用recursion向左和右分别遍历。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int max = 0;
public int maxPathSum(TreeNode root) {
if(root == null) return 0;
max = Integer.MIN_VALUE;
maxPath(root);
return max;
}
private int maxPath(TreeNode root){
if(root == null) return 0;
int left = Math.max(maxPath(root.left), 0);
int right = Math.max(maxPath(root.right), 0);
max = Math.max(max, left + right + root.val);
return Math.max(left, right) + root.val;
}
}
O(n), O(height of the tree) 时间是遍历到了每个节点，递归的空间花销是树的高度，我也不知道高度是多少_(:з」∠)_
今天得到梦碎的消息(._.) 虽然知道自己实力还不够题还没刷好不过还是很难过啦…感觉拜托学长推上去却挂掉了好丢脸啊… 深知此事不易，本不奢求一帆风顺，也免不了难过一下……