(Leetcode) 124 - Binary Tree Maximum Path Sum

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice

주간 미션을 마쳤기 때문에 시간이 남아서 뒤에서 한문제를 골라 풀기로 하였다.

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

이 문제는 hard 문제이다. 굉장히 어려웠다. 아무리 생각해도 효율적인 방법이 생각나지 않아서 솔루션을 확인하였다. 다음에 꼭 다시 풀어봐야겠다.

모범 답안

문제에서 어려웠던 부분은 ‘ㅅ’ 모양으로도 path가 설정될 수 있다는 것이였다.

문제에서 제공된 binary tree는 위에서 아래로 내려갈수는 있지만 다시 올라갈수는 없는 구조였다. 그래서 root에서 시작해야 한다는 것 정도는 힌트로 얻을 수 있었었다.

class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPath(TreeNode root) {
        if(root == null) return 0;

        int value = root.val;

        int left_sum = Math.max(maxPath(root.left),0);
        int right_sum = Math.max(maxPath(root.right),0);

        max = Math.max(max, left_sum + right_sum + value);

        return Math.max(left_sum, right_sum) + value;
    }

    public int maxPathSum(TreeNode root) {
        maxPath(root);
        return max;
    }
}

‘ㅅ’ 자 모양으로 계산했을 때의 값은 max에 보관한다. 부모 노드에는 왼쪽과 오른쪽 중에서 큰 값과 자신의 값을 더한 값을 전달해준다. 이를 통해서 path가 중복되지 않으면서 계산을 할 수 있다.

TC, SC

시간 복잡도는 O(n)이고, 공간 복잡도는 O(n), 단 입력 트리가 balanced되어 있다면 O(log n)이다.