124. Binary Tree Maximum Path Sum - Streak 11

이번 문제는 과거에 풀었던 문제와 굉장히 유사했지만, 약간의 차이가 있었다.
이번 문제는 "부분 집합"이 아닌, "경로"를 탐색하는 문제였다.

 

따라서 한가지 추가 처리가 필요했다.
그 추가 처리란, 다음과 같은 두 상황의 분리였다.

• 최댓값을 구하는 시점
• 부모 노드에 자신의 최댓값을 전달하는 시점

최댓값을 구하는 시점

최댓값을 구하는 시점에는, 자신을 거쳐서 반대편 노드로 가는 경로에 대한 계산을 위해, 다음과 같은 네 가지 케이스의 처리가 필요했다.

• 자기 자신 단독
• 왼쪽 - 자기 자신
• 오른쪽 - 자기 자신
• 왼쪽 - 자기 자신 - 오른쪽

부모 노드에 자신의 최댓값을 전달하는 시점

하지만 부모노드에 자신의 최댓값을 전달하는 시점에는, "왼쪽-자기 자신-오른쪽-부모 노드"와 같은 경로 처리가 불가능하므로, 이를 제외해줘야 했다.

• 자기 자신 단독
• 왼쪽 - 자기 자신
• 오른쪽 - 자기 자신

/**
 * 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 {
    int max = 0;
    public int maxPathSum(TreeNode root) {
        max = root.val;
        dfs(root);
        return max;
    }
    public int dfs(TreeNode node){
        int left = 0, right = 0;
        if(node.left != null) left = dfs(node.left);
        if(node.right != null) right = dfs(node.right);
        int now = node.val;
        now = Math.max(now, left + node.val);
        now = Math.max(now, right + node.val);
        max = Math.max(max, now);
        max = Math.max(max, left + right + node.val);
        System.out.println(now);
        return now;
    }

    /**
    왼쪽 최대 합
    오른쪽 최대 합

    왼쪽 - 나: 넘기기 가능
    나 - 오른쪽: 넘기기 가능
    왼쪽 - 나 - 오른쪽: 넘기가 불가능
     */
}