Binary Tree Maximum Path Sum LeetCode solution in Java

1
class Solution {
2

3
  int[] ans = new int[1];
4

5
  public int maxPathSum(TreeNode root) {
6
    ans[0] = root.val; // Handle edge case
7
    dfs(root);
8
    return ans[0];
9
  }
10

11
  public int dfs(TreeNode root) {
12

13
    if (root == null) return 0;
14

15
    int left =
16
        Math.max(0, dfs(root.left)); // Check on the left subtree and if returned negative take 0
17
    int right =
18
        Math.max(0, dfs(root.right)); // Check on the right subtree and if returned negative take 0
19

20
    int maxInTheNode =
21
        root.val + left
22
            + right; // Calculating the max while including the root its left and right child.
23
    ans[0] = Math.max(ans[0], maxInTheNode); // Keeping max globally
24

25
    return root.val
26
        + Math.max(
27
            left,
28
            right); // Since only one split is allowed returning the one split that returns max
29
    // value
30
  }
31
}