[DP, Tree] House Robber III

node가 집이고 도둑이 여기를 순회하면서 node의 value만큼 돈을 훔친다.

이때 바로 옆집을 훔치면 경찰에 잡혀서, 한칸이상 떨어진 집의 돈을 훔쳐야 할 때, 총 얼마나 훔칠 수 있는지 구하라는 문제

 

하나의 node에 방문했을 때, 그 node의 집을 훔치기로 한다면 r, 아니라면 n이라고 하자

leaf라면 [0,0]이 되겠지만, 그것이 아니라면 [ 훔치기로 함, 안훔치기로 함]이 된다

훔치기로 하면 그 node의 value를 리턴해주면 된다.

안훔치기로 했으면 그 아래 노드의 최댓값을 리턴해준다