/**
A path in a binary tree is a sequence of nodes where each pair of adjacent
nodes in the sequence has an edge connecting them. A node can only appear in the
sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node's values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty
path.
Example 1:
Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 =
42.
Constraints:
The number of nodes in the tree is in the range [1, 3 * 10⁴].
-1000 <= Node.val <= 1000
Related Topics树 | 深度优先搜索 | 动态规划 | 二叉树
👍 1691, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
getMaxSum(root);
return result;
}
private int result = Integer.MIN_VALUE;
private int getMaxSum(TreeNode node) {
int leftMax = 0, rightMax = 0;
if (node.left != null) {
leftMax = getMaxSum(node.left);
}
if (node.right != null) {
rightMax = getMaxSum(node.right);
}
int maxPath = node.val;
if (leftMax > 0 ) {
maxPath += leftMax;
}
if (rightMax > 0) {
maxPath += rightMax;
}
if (maxPath > result) {
result = maxPath;
}
if (leftMax > rightMax && leftMax > 0) {
return node.val + leftMax;
} else if (rightMax > leftMax && rightMax > 0) {
return node.val + rightMax;
} else {
return node.val;
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
