124 Binary Tree Maximum Path Sum
124. Binary Tree Maximum Path Sum
1. Question
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
Return6
.
2. Implementation
(1) DFS
class Solution {
public int maxPathSum(TreeNode root) {
int[] max = new int[1];
max[0] = Integer.MIN_VALUE;
findMaxPathSum(root, max);
return max[0];
}
public int findMaxPathSum(TreeNode node, int[] max) {
if (node == null) {
return 0;
}
int leftPathSum = Math.max(0, findMaxPathSum(node.left, max));
int rightPathSum = Math.max(0, findMaxPathSum(node.right, max));
max[0] = Math.max(max[0], node.val + leftPathSum + rightPathSum);
return node.val + Math.max(leftPathSum, rightPathSum);
}
}
3. Time & Space Complexity
(1) DFS: 时间复杂度: O(n), 空间复杂度: O(h)
Last updated
Was this helpful?