leetcode: Binary Tree Maximum Path Sum

이 문제는 트리를 어떤 방식으로든 순회했을 때, 그 합의 최대를 구하는 문제이다.

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

예를 들어 위 예제의 경우 최적의 순회 방법중 하나는 15 -> 20 -> 7 이고 그 합은 15 + 20 + 7 = 42이다.

 

먼저 저번에 공부했던 tree dp처럼 어떤 노드를 기준으로 해당 서브 트리의 최대값을 구할 수 있도록 하자고 생각했다.

즉, 리프 노드의 경우는 해당 노드에 적혀있는 수를 리턴하고,

그 이외는 아래에서부터 올라오면서 최대 값을 해당 노드에 저장하는 식이다.

 

이러한 경우 시간복잡도는 O(N)으로 볼 수 있으며 풀이는 아래와 같다.

class Solution {
	int answer = Integer.MIN_VALUE;

	public int findMaxNode(TreeNode node) {
		if (node == null) {
			return 0;
		}

		int leftValue = Math.max(findMaxNode(node.left), 0);
		int rightValue = Math.max(findMaxNode(node.right), 0);

		int newValue = node.val + leftValue + rightValue;

		answer = Math.max(answer, newValue);

		return node.val + Math.max(leftValue, rightValue);
	}

	public int maxPathSum(TreeNode root) {
		findMaxNode(root);
		return answer;
	}
}