[알고리즘] 10번째 문제

337. House Robber III
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 Data{
    int selected;
    int notSelected;

    public Data(){}
    public Data(int selected, int notSelected){
        this.selected = selected;
        this.notSelected = notSelected;
    }
}

class Solution {
    public int rob(TreeNode root) {
        Data rootResult = getMaxMoney(root, 1);
        return Math.max(rootResult.selected, rootResult.notSelected);
    }

    public Data getMaxMoney(TreeNode node, int idx){
        if(node == null){
            return new Data(0,0);
        }

        // 리프 노드의 경우
        if(node.left == null && node.right == null){
            return new Data(node.val, 0);
        }

        Data leftResult = getMaxMoney(node.left,idx*2);
        Data rightResult = getMaxMoney(node.right,idx*2+1);

        Data result = new Data();
        // i번째를 선택하지 않는 경우는 자식 노드를 선택하지 않거나, 선택했을 때의 더 큰 값
        result.notSelected = Math.max(leftResult.notSelected,  leftResult.selected) + Math.max(rightResult.notSelected, rightResult.selected);
        // i번째를 선택하는 경우는 자식 노드를 선택하지 않았을 때의 가장 큰 값
        result.selected = leftResult.notSelected + rightResult.notSelected + node.val;

        return result;
    }
edu-pi / SOMA

[알고리즘] 10번째 문제 #102

📝 Description

❗️Todo

ETC
