[greedy] 337. House Robber III

문제

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return *the maximum amount of money the thief can rob without alerting the police*.

도둑은 다시 도둑질을 위한 새로운 장소를 찾았다. 이 지역에는 루트라고 불리는 입구가 하나밖에 없다.

뿌리 이외에 각 집에는 하나의 부모 집이 있다. 여행을 한 후, 똑똑한 도둑은 이곳의 모든 집들이 이진수를 이루고 있다는 것을 깨달았습니다. 이날 밤 직결주택 2채가 침입하면 자동으로 경찰에 연락한다.

바이너리 트리의 루트가 주어지면 도둑이 경찰에 알리지 않고 강탈할 수 있는 최대 금액을 돌려준다.

예시

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

제약

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 104

코드

const traverse = (node) => {
    if (!node) {
        return { current: 0, next: 0 };
    }

    const left = traverse(node.left);
    const right = traverse(node.right);

    const current = node.val + left.next + right.next;
    const next = Math.max(left.current, left.next) + Math.max(right.current, right.next);

    return { current, next };
}

const rob = (root) => {
    const { current, next } = traverse(root);

    return Math.max(current, next);
};

아래 블로그를 참고하였습니다.

https://dev.to/cod3pineapple/leetcode-337-house-robber-iii-javascript-solution-531g

• dfs, 재귀로 다음 노드들을 순회하며 현재 집을 털었을 때와 현재 집을 털지 않았을 때를 구해오는 방식이다.

• 현재집을 턴다는것은 현재의 집의 value와 다음집의 다음 집을 털었을 때의 값들을 합칠 때이다.

  • const current = node.val + left.next + right.next;

• 다음 집을 턴다는것은 왼쪽 아랫집을 털었을 때와 안털었을때 중의 최대값 + 오른쪽 집을 털었을때 안털었을 때 중에 최대값 이다.

  • const next = Math.max(left.current, left.next) + Math.max(right.current, right.next);