[Leetcode] 124. Binary Tree Maximum Path Sum - JS

https://leetcode.com/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
노드는 최대 1번만 나타날 수 있다.
경로는 루트를 반드시 통과할 필요는 없다.
경로의 합계는 노드 값의 합계이다.
이진 트리의 루트가 주어질 때, 비어 있지 않은 경로의 최대 합계를 반환하라.

제한조건
--------------------
- 노드의 갯수는 1 ~ 3*10^4개이다.
- -1000 <= Node.val <= 1000

 

2. 접근 방법

접근방법
--------------------
모든 경로 중 경로에 포함된 노드의 합이 최댓값을 반환해야한다.

왼쪽 서브트리에서 최대 경로의 합, 오른쪽 서브트리에서 최대 경로의 합에
자기 자신 노드의 값을 더한 값 중 최댓값을 구하면 된다.

만약 서브트리의 합이 더 클수도 있으니 max 값은 모든 경로에서 최댓값으로 갱신해줘야한다.
또한, 서브트리의 값이 음수일 경우는 경로의 최댓값을 구하는데 불필요하니, 0으로 바꿔준다.

helper 함수는 경로의 최댓값을 갱신해주는 역할과 서브트리의 경로 중 최댓값을 반환하는 역할을 한다.

 

 

3. 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var maxPathSum = function(root) {
    let maxSum = -Infinity;

    function helper(node) {
        if (!node) return 0;

        let leftMaxPath = Math.max(helper(node.left), 0);
        let rightMaxPath = Math.max(helper(node.right), 0);

        let currentMaxPath = node.val + leftMaxPath + rightMaxPath;
        maxSum = Math.max(maxSum, currentMaxPath);

        return node.val + Math.max(leftMaxPath, rightMaxPath);
    }

    helper(root)

    return maxSum;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

Hard 문제 치고 그렇게 어렵지는 않았던 것 같다.

어떻게 풀어야할 지 큰 틀에서 이해는 했지만, 재귀함수를 구현하는데 어려움이 있었다.

GPT를 통해서 문제를 정확히 파악하여 경로가 모든 경로를 의미하는 것을 알고 난 후 문제를 보니 이해가 더 쉬웠다.

 

maxSum 변수를 선언하고 재귀함수에서 maxSum을 갱신하면서 재귀호출하는 것은 이해했다.

경로의 값 중에서 어떻게 최댓값을 구할 수 있는지가 미지수였다.

방법은 왼쪽 서브트리와 오른쪽 서브트리 중 최댓값을 구하고 자기 자신의 node 값을 더한 값이 최댓값일 때를 구하면 된다.

 

왼쪽 서브트리와 오른쪽 서브트리의 최댓값을 구하기 위해서는

자식의 서브트리를 재귀적으로 타고 가서 최댓값을 구해야하므로

left, right 서브트리에 재귀로 함수를 호출해준다.

이 때, 서브트리의 합이 음수이면 굳이 경로에 포함시킬 필요가 없으므로 0으로 바꿔준다.