Leet code (Hard): 124. Binary Tree Maximum Path Sum - Java

 

어떻게 풀어야할지 모르겠었던 문제.

 

리프 노드부터 돌며,

현재 노드를 최고 높은 루트 노드로 하여 순회한다고 할 때의 최댓값을 구하면 된다.

 

아래 두가지를 생각했다.

 

1) 재귀식과 리턴값 정하기

그럼 재귀식이 필요한데.

재귀식이 return 하는 값은 현재 노드까지의 최대값을 리턴하면 된다.

그 값은 ~

자식 노드가 left, right 두개이니,

1. left 자식 노드까지의 값 (leftSum)
2. right 자식 노드까지의 값 (rightSum)

두 값 중 최대값에 현재 노드(root)의 value를 더한값을 리턴하면 된다.

 

2) 전체 최댓값 갱신 어떻게 할지 정하기

그리고 매 root 마다,

위 값 말고 현재 노드(root)가 최상위 노드가 될 경우에 대한 값(left 자식노드 합 + right 자식 노드 합 + 자기 자신 value)을

구하여 전체 최대값과 비교해서 전체 최댓값을 갱신 해야한다.

/**
 * 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 {
    public int maxPathSum(TreeNode root) {
        
        int[] maximum = new int[1];

        // 재귀속에서 합을 계속 들고다니기 위해 배열에 넣어둠.
        maximum[0] = Integer.MIN_VALUE;

        findMaxPathSum(root, maximum);
        
        return maximum[0];
    }

    private int findMaxPathSum(TreeNode root, int[] maximum){
        if(root == null) return 0;

        int leftSum = Math.max(0, findMaxPathSum(root.left, maximum));

        int rightSum = Math.max(0, findMaxPathSum(root.right, maximum));

        // 현재 노드인 root를 가장 높은 노드로 할 경우의 값과 전체 최댓값을 비교해서
        // 전체 최댓값 갱신
        maximum[0] = Math.max(maximum[0], leftSum + rightSum + root.val);

        // left, right 중 더 큰값과 root를 합한 값을 리턴
        // root까지의 최대값임.
        return root.val + Math.max(leftSum, rightSum);
    }
}