[Binary Search][Hard] 124. Binary Tree Maximum Path Sum

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

 

Q. 한 노드에서 다른 노드까지의 과정을 경로라고 할때, 이 경로의 과정 중, 최대 합을 구하라. 

 경로에서 모든 노드는 한번씩만 등장 할 수 있다. 

 

 

Solution. 

 특정 노드 기준, 왼쪽경로 + 오른쪽경로 + 노드값 이 값의 최대값을 구하라는 것이다. 

 따라서 이 값이 최대값인지 확인하려면, 결국 모든 노드에 대해 이 계산을 해야 할 것이다. 

 일단 leaf 노드는 자신의 값이 최종 최대값이 될 것이다. 

 이를 염두하고 모든 노드에 대해 이 연산을 할 수 있다. 

 또한 윗 노드에서도 현재노드의 값을 이용해서 같은 연산을 해야 한다. 

 따라서 윗 노드에는 한쪽 최대값과 현재노드 합 중 큰 녀석을 반환한다. 그래서 윗 노드가 필요한 값을 구할때 이 값을 참조 하도록 한다. 

 

 글로 쓰니 좀 지지부진 한데, 이를 로직으로 써 본다. 

 

    int maxPathSumBS(TreeNode* node, int& maxSum)
    {
        if (node == NULL)	return 0;

        int leftMax = 0;
        int rightMax = 0;
        
        // 좌나, 우가 음수가 되면, 가지 않는 것이 최대일 것이다. 따라서 양수일 경우만 취한다.
        if (node->left != NULL)
            leftMax = max(leftMax, maxPathSumBS(node->left, maxSum));
        if(node->right != NULL)
            rightMax = max(rightMax, maxPathSumBS(node->right, maxSum));
        
        // maxSum은 모든 노드에 대해 계산해 준다.
        maxSum = max(maxSum, leftMax + rightMax + node->val);
        
        // 상위 노드에는 양쪽 중 더 큰 값에 의한 결과 전달한다.
        return leftMax > rightMax ? leftMax + node->val : rightMax + node->val;
    }
public:
    int maxPathSum(TreeNode* root) 
    {
        int maxSum = INT_MIN;
        maxPathSumBS(root, maxSum);
        return maxSum;
    }

 

적절한 결과를 얻었다.