LeetCode 337. House Robber III

문제 요약: 이진 트리가 주어졌을때 서로 인접하지 않는 노드들의 최대값을 구하시오.

 

예:

input : [3,2,3,null,3,null,1]

output: 7

 

input: [3,4,5,1,3,null,1]

output: 9

 

문제 접근: root 노드부터 자기자신을 포함했을때와, 안포함했을때의 값을 저장해 둔다음, 자식노드의 값을 비교하여 마지막 노드까지 내려간다. 처음 예제에서 3과 2+3을 가지고 있고 그 자식노드에서 3+3+1과 2+3를 저장해두고 또 자식노드로 가서 비교를 하는 방식으로 구현하면 될 거 같다.

 

구현 코드:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	public int[] rob(TreeNode root) {
    	// answer의 배열의 원소에는 0번 인덱스는 자기자신을 포함할 경우,
        // 1번 인덱스는 자기자신을 포함하지 않는 경우이다.
    	int[] answer = this.getMaximumSumOfNode(root);
        return Math.max(answer[0], answer[1]);
    }
    
    public int[] getMaximumSumOfNode(TreeNode node) {
    	// 기본값 초기화
    	int[] result = new int[]{0,0};
        if (node == null) return result;
        // 만약 자식 노드들이 없다면 자기자신의 값이 최대값이므로,
        // 자기자신이 포함될 경우인 0번인덱스에 자기자신의 값을 세팅하고 반환
        if (node.left == null && node.right == null) {
        	result[0] = node.val;
            return result;
        }
        // 왼쪽 자식노드 부터의 최대값을 구한다.
        int[] leftNodeResult = this.getMaximumSumOfNode(node.left);
        // 마찬가지로 오른쪽 노드도 똑같이 한다.
        int[] rightNodeResult = this.getMaximumSumOfNode(node.right);
        
        // 자식노드의 최대값을 구한다.
        int leftMaxSum = Math.max(leftNodeResult[0], leftNodeResult[1]);
        int rightMaxSum = Math.max(rightNodeResult[0], rightNodeResult[1]);
        
        // 자기자신을 포함할때는 자식노드에서 자식노드 자신이 포함안될경우를 더하고,
        // 자기자신을 포함안할때는 자식노드의 최대값을 세팅하면 된다.
        result[0] = lefNodeResult[1] + rightNodeResult[1] + node.val;
        result[1] = leftMaxSum + rightMaxSum;
    	return result;
    }
}

트리관련 문제는 많이풀어봐야 이해하기가 쉽다.