Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

문제 내용

왼쪽에서 오른쪽으로 한개의 라인으로 이었을때 가장 큰 값은?

 

접근 방법

문제를 이해하기 쉽지 않다.

예제의 Depth가 최대 1 depth로 표현 되어있기 때문이다.

Testcase를 돌려보면 몇개의 Depth가 되든 상관없이 왼쪽의 노드에서 오른쪽 노드까지의 Sum이 최대가 되면 된다.

예를 들자면 다음과 같다.

즉 양수이기만 한다면 left child와 right child 중 가장 큰값을 기준으로 sum을 하면 된다.

이런 그림인데 이 그림으로 인해서 혼돈이 발생 할 수도 있는데, 만약 다음과 같은 경우라면

$$ 3 $$ 이 답이 된다.

즉 어떤 Path든 상관없이 왼쪽 오른쪽의 0이상의 Max 값을 더해서 최고가 되는 값을 구하면 된다.

var maxPathSum = function(root) {

    let maxValue = root.val;
    
    let helper = function(node){
        
        if(node === null) return 0;
        
        let centerVal = node.val;
        
        let leftMax = Math.max(helper(node.left),0);
        let rightMax = Math.max(helper(node.right),0);
        let curVal = centerVal +  leftMax + rightMax;
        
        maxValue = Math.max(curVal, maxValue);
        
        return centerVal + Math.max(leftMax ,rightMax);
    }
    
    helper(root);
    
    return maxValue;
    
};

모든 노드를 한번씩만 돌게 됨으로

$$ O(N) $$

이다.