[leetCode] 124. Binary Tree Maximum Path Sum

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

Binary Tree Maximum Path Sum - LeetCode

 

이진 트리 경로에 존재하는 노드 값들의 합이 최대 경로 합을 반환하는 문제이다

 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int* num = new int(-1001);
        search(root, num);
        return *num;
    }

    int search(TreeNode* root, int* num)
    {
        if(root == nullptr) 
            return 0;
        
        int leftSum = max(0, search(root->left, num));
        int rightSum = max(0, search(root->right, num));

        int lastSum = root->val + leftSum + rightSum;
        
        if(*num<lastSum)
            *num = lastSum;
        
        return root->val + max(leftSum, rightSum);
    }
};

 

결국 최대 경로의 합을 구하는 것이므로, 만약 해당 노드에 마이너스(-)가 나온다면 max 함수로 0으로 만들고,  굳이 음수를 더하지 않는다. 그렇게 하위 노드들을 더하고, root 노드까지 살펴봐, 경로상의 큰 수를 구한다. (후위 순열)

 

 하위 경로부터, 상위 경로의 노드까지 살펴봐야 하므로, 마지막에, 해당 노드 + left냐, right냐를 max함수로 따져서 더하고, 상위 노드로 이동하여 비교를 계속 실행한다.