leetcode 124 - Binary Tree Maximum Path Sum

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

풀이

sum이 가장 큰 경로가 있다면 그 경로의 시작점, 끝점은 어느 루트를 통해 연결되어 있을 것이다. 즉, 모든 노드에 대해 왼쪽에서 최선의 경로 + 오른쪽에서 최선의 경로 + 자신의 최댓값을 찾아본다. 이때 왼쪽, 오른쪽의 경로는 어느 루트 노드를 통해 꺾인 값이면 연결이 불가능하기 때문에 child 방향으로 일직선으로만 이루어진 경로여야 한다.

 

이렇게 식을 세우면 재귀 함수를 통해 return값으로 자기 자신을 포함해서 child 방향으로만 이루어진 최댓값을 넘겨서 양쪽 자식의 return값 + 자신의 값을 비교해서 답을 찾는다.

 

코드

class Solution {
public:
    int ans = -1000;
    int maxPathSum(TreeNode* root) {
        find(root);
        return ans;
    }
private:
    int find(TreeNode* root) {
        if(root == nullptr) return 0;
        int l = max(find(root->left), 0);
        int r = max(find(root->right), 0);
        ans = max(ans, l + r + root->val);
        
        return max(l, r) + root->val;
    }
};