[Algorithm][Tree][Java] 문제 풀이 #25 - 124. Binary Tree Maximum Path Sum

문제 링크

https://leetcode.com/problems/binary-tree-maximum-path-sum/

내 풀이

int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    if(root.left == null && root.right == null) return root.val;
    recursion(root);
    return max;
}

private void recursion(TreeNode node) {
    if(node == null) return;
    if(node.left == null && node.right == null) return;

    int leftVal = node.left != null ? node.left.val : Integer.MIN_VALUE;
    int rightVal = node.right != null ? node.right.val : Integer.MIN_VALUE;

    max = Math.max(max, getMaxValue(node.val, leftVal, rightVal));
    recursion(node.left);
    recursion(node.right);
}

private int getMaxValue(int nodeVal, int leftVal, int rightVal) {
    int sumLeftVal = leftVal == Integer.MIN_VALUE ? 0 : leftVal;
    int sumRightVal = rightVal == Integer.MIN_VALUE ? 0 : rightVal;
    int maxSum = Math.max(nodeVal + sumLeftVal + sumRightVal, Math.max(nodeVal + sumLeftVal, nodeVal + sumRightVal));
    int tmpMax = Math.max(nodeVal, Math.max(leftVal, rightVal));
    return Math.max(maxSum, tmpMax);

}

내 풀이 결과

정답 풀이

int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    Math.max(max, recursion(root));
    return max;
}

private int recursion(TreeNode node) {
    if(node == null) return 0;

    int leftVal = Math.max(0, recursion(node.left));
    int rightVal = Math.max(0, recursion(node.right));
    max = Math.max(leftVal + rightVal + node.val, max);
    return Math.max(leftVal, rightVal) + node.val;
}

대충 반절정도 맞았다는 것에 대해서 위안을 느끼지만 문제를 좀 더 자세히 읽어 봤다면 정답 풀이에 가깝게 문제를 해석하고 답도 맞췃을 거라고 생각된다. 아직은 멀었네...