[LeetCode] 337. House Robber III

😎풀이

1. 깊이 우선 탐색 실행
   1-1. 노드가 존재하지 않을 경우 훔치거나 훔치지 않거나 돈을 벌지 못함 [0, 0]
   1-2. 좌측 깊이 우선 탐색으로 훔치거나 훔치지 않았을 때의 최댓값 산정
   1-3. 우측 깊이 우선 탐색으로 훔치거나 훔치지 않았을 때의 최댓값 산정
   1-4. 현재 노드를 훔칠거라면, 자식 노드의 훔치지 않은 경우와 현재 노드의 값을 합함
   1-5. 현재 노드를 훔치지 않을거라면, 자식 노드의 훔치거나 훔치지 않은 값 중 최댓 값을 합함
2. 훔치거나 훔치지 않은 값 중 최댓값 반환

function rob(root: TreeNode | null): number {
    function dfs(node: TreeNode | null) {
        if(!node) return [0, 0];
        const [leftRobbed, notLeftRobbed] = dfs(node.left)
        const [rightRobbed, notRightRobbed] = dfs(node.right)
        const robbed = node.val + notLeftRobbed + notRightRobbed
        const notRobbed = Math.max(leftRobbed, notLeftRobbed) + Math.max(rightRobbed, notRightRobbed)
        return [robbed, notRobbed]
    }
    const [robbed, notRobbed] = dfs(root)
    return Math.max(robbed, notRobbed)
};