(Tree, Hard) Binary Tree Maximum Path Sum

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

경로 중 최대값을 찾는 문제다.
핵심은 아래와 같다.

• Q. 어떻게 노드 별 최대 경로값을 찾나?
  A. 후위 순회로 left + right 값을 구하고 현재 node의 값을 더해서, 본 node가 root인 서브트리에서의 경로 최대값을 갱신해나갈 수 있다.

• Q. 이것을 기반으로 부모로까지 확장은 어떻게 이루어지나?
  A. 리턴 시 left와 right중 큰 값을 선택한다. 즉, 최대값이 될 수 있는 경로를 왼쪽과 오른쪽 둘 중 하나만 선택해 본 node의 val과 더해서 리턴한다.
  즉, node에서 이어질 수 있는 최대 경로를 선택하는 행위

이 과정에서 후위 순회 시 left 혹은 right의 값이 음수라면
더해봤자 손해이므로 0으로 치환해서 버린다 (아예 안 간 것처럼 처리: 경로에 포함 안함).

class Solution {

    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = Math.max(0, dfs(node.left));
        int right = Math.max(0, dfs(node.right));

        int sum = node.val + left + right;
        max = Math.max(max, sum);

        return node.val + Math.max(left, right);
    }
}

이 문제도 입력값에 노드가 최대 3만개가 될 수 있다고 해서 재귀로 가능한가 싶었는데..
최대한 균형이 맞는 이진트리를 주나보다.

다른 글에서도 언급했지만 StackOverFlow 무서우면 회피용으로 별도 자료구조 (Stack이나 Deque) 쓰면 된다.