[LeetCode, 124] Binary Tree Maximum Path Sum

 

public int getMax(TreeNode node) {
    if (node == null) {
        return 0;
    }
    int leftVal = Math.max(0, getMax(node.left));
    int rightVal = Math.max(0, getMax(node.right));

    max = Math.max(max, node.val + leftVal + rightVal);

    return node.val + Math.max(leftVal, rightVal);
}

 

이어진 노드중 가장 큰 값을 구하는 문제로 먼저 재귀 호출을 계속 하면서 트리 끝까지 이동한다.

 

끝에서부터 음수인 값(leftVal, rightVal)은 더하지 않고 양수인 값만 더해간다.

 

반환하기 전에 해당 노드 기준으로 max 값을 갱신

 

자식 노드가 양수더라도 부모 노드 음수 값이 더 크면 해당 노드는 짤린다.

 

중간에 아니다 싶을때 뚫린 구멍 막는 식으로 풀지 말고 다시 생각해보기..!

 

Binary Tree Maximum Path Sum - LeetCode