Binary Tree Maximum Path Sum

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

Binary Tree Maximum Path Sum - LeetCode

 

주어진 이진 트리 노드를 하나의 길로 연결 했을 때 가장 큰 누적 합의 값을 찾는 문제이다.

 

특정 노드에서 길을 잇기 위해선 좌우 노드와 이어지거나, 좌 또는 우 노드 중 하나와 상위 노드와의 연결이 되는 경우이다. 이러한 규칙으로 재귀적으로 순환하며 특정 노드에서 좌,우 노드와의 합계의 최대 값을 결과 값으로 구할 수 있다.

 

아래는 통과된 코드이다. 주의할 점은 return 해서 상위 노드로 보내는 값과 해당 노드에서 가능한 최대 값의 계산 방식이 다르다는 점이다.

class Solution {  
  
    int answer;  
  
    public int maxPathSum(TreeNode root) {  
        this.answer = Integer.MIN_VALUE;  
        recursiveNode(root);  
        return answer;  
    }  
  
    public int recursiveNode(TreeNode root){  
  
        if(root == null) return 0;  
  
        int val1 = root.val;  
        int val2 = Math.max(recursiveNode(root.left), 0);  
        int val3 = Math.max(recursiveNode(root.right), 0);  
  
        int maxValue = val1 + val2 + val3;  
        answer = Math.max(maxValue, answer);  
  
        return val1 + Math.max(val2, val3);  
    }  
}