[LeetCode] 124. Binary Tree Maximum Path Sum

😎풀이

DFS를 통해 루트부터 서브트리를 따라가며, 계산한 합으로 나올 수 있는 최대치를 반환하는 문제이다.

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxPathSum(root: TreeNode | null): number {
    // 전역 변수로 최대 경로 합을 추적
    let maxSum = -Infinity;
    
    // DFS(깊이 우선 탐색)를 수행하는 헬퍼 함수
    const findMaxPath = (node: TreeNode | null): number => {
        // 기저 사례: null 노드를 만나면 0을 반환
        if (!node) return 0;
        
        // 왼쪽 서브트리의 최대 경로 합을 계산
        // 음수인 경우 0을 사용 (해당 경로를 무시)
        const leftMax = Math.max(findMaxPath(node.left), 0);
        
        // 오른쪽 서브트리의 최대 경로 합을 계산
        // 음수인 경우 0을 사용 (해당 경로를 무시)
        const rightMax = Math.max(findMaxPath(node.right), 0);
        
        // 현재 노드를 포함하는 경로의 최대 합을 계산
        // (왼쪽 경로 + 현재 노드 + 오른쪽 경로)
        const currentPathSum = leftMax + node.val + rightMax;
        
        // 전역 최대값 업데이트
        maxSum = Math.max(maxSum, currentPathSum);
        
        // 상위 노드로 전파할 최대 합을 반환
        // (현재 노드와 왼쪽 또는 오른쪽 경로 중 하나만 선택)
        return node.val + Math.max(leftMax, rightMax);
    };
    
    // 루트부터 DFS 시작
    findMaxPath(root);
    
    return maxSum;
}