Binary Tree Maximum Path Sum

트리 내에 존재하는 엣지 를 타고 가장 합이 높은 부분을 구하는 문제이다. 어제와 유사한 문제라고 생각해서 비슷하게 접근했으나 머리가 대차게 깨져버렸다.

어제 와 유사한 코드로 접근하였으나 - 값의 여부와 한가지 패스 안에서는 길을 타고 다시 거슬러 올라오면 안 된다는 부분에서 신경이 쓰여 preorder를 사용했다. 중복을 처리해줄 방법이 없어 생각보다 애를 많이 먹었다... 

if를 이용해서 틀릴 때마다 처리를 해주었으나. 99개 테스트 케이스에서 56 이 한계였다. preOrder, postOrder 전부 실패했다. prefix를 이용하기 위해 리스트 넘기는 방법, max를 이용해 현재 비교대상을  3번 비교하는 방법 전부 실패했다.

뭔가 잡힐듯 말듯한데 자꾸 실패해서 분하다...

 

약 1시간 정도 풀다가 실패해서 discuss를 보고 오니 내가 구해야 할 명확한 목적을 알고 나니 풀이가 쉬워졌다.

 

머리 깨진 풀이

class Solution {
    int max;
    public int maxPathSum(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        max = Integer.MIN_VALUE;
        helper(root, list);
        int total = list.get(list.size()-1);
        for (int i = 0; i < list.size()-1; i++) {
            max = Math.max(Math.max(total,total-list.get(i)),max);
        }
        return max;
    }

    public void helper(TreeNode node, List<Integer> list){
        if(node == null) return;
        helper(node.left, list);
        int previous = list.size() == 0 ? 0 : list.get(list.size()-1);;
        list.add(previous+node.val);
        max = Math.max(max,node.val);
        helper(node.right,list);
    }
}

트리 순회를 위해 helper를 선언해 중위 순회를 선택했다. 이유는 후위 순회를 하게 된다면 리프부터 타고 올라가야 하는데 이 기준점을 정해주기 가 생각보다 어려웠다. prefix를 사용해야 한다는 압박감 때문 인지. 후위 순회를 하게 되니 오류가 많이 생겼다. 

디스커스에서 읽고 바로 풀이 방법을 바꾼 힌트 를 보자.

우리가 구해야 할 4가지 경우의 수가 있다.

1. 왼쪽 패스 + 현재 값

2. 오른쪽 패스 + 현재 값

3. 왼쪽 패스 + 오른쪽 패스 + 현재 값

4. 현재 값 자체로 위 값보다 큰 경우

이 4 가지를 명확히 하고 갔어야 했는데 이게 안되니 null 이 여러 번 들어간 깊이 있는 트리인 경우 오답이 나게 되는 것이다. ㅠ

 

위 4가지 힌트를 얻어서 작성한 풀이법이다. 

class Solution{
	int max = Integer.MIN_VALUE;
    
	public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    public int helper(TreeNode node){
    	if(node == null) return Integer.MIN_VALUE;
        int left = helper(node.left);
        int right = helper(node.right);
        
        max = Math.max(max,Math.max(left,right));
        max = Math.max(max,node.val);
        max = Math.max(max,node.val+Math.max(left,0)+Math.max(right,0));
        return node.val + Math.max(0,Math.max(left,right));
    }
}

max 값을 비교할 Integer를 선언해주고 , 현재 값이 - 값이라면 무조건 0으로 초기화시켜주었다. 

left 패스, right 패스를 각각 구하고 현 max와 패스의 합 +현재 값

그리고 현재 값에 패스 값 중 높은 값을 다음으로 넘겨주는 재귀를 작성하였다. 

 

class Solution{
	int value = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        int temp = process(root);
        return Math.max(temp, value);
    }

    public int process(TreeNode head){
        if(head == null){
            return 0;
        }
        int leftTree = Math.max(0, process(head.left));
        int rightTree = Math.max(0, process(head.right));
        value = Math.max(value, leftTree + rightTree + head.val);
        return Math.max(leftTree, rightTree) + head.val;
    }
}

이 사람도 보면 참 깔끔하게 작성한 거 같다. 왼쪽 패스, 오른쪽 패스를 나누고 현재 값의 맥스를 왼쪽 오른쪽의 합과 현재 값을 이용하고 다음 재귀로 왼쪽 오른쪽 중 큰 값을 현재 값에 더해 넘겨준다.

 

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

작성할 때 난감 했던 부분이다. maxVaule를 현재 와 왼쪽 오른쪽 그리고 노드의 값을 합친 값으로 업데이트를 하는 것이 아닌가.

문제의 포인트를 잡지 못해서 이상한 풀이법으로 나가 결국 맞지 못한 문제였다.