[Leetcode] 337. House Robber III

문제 : https://leetcode.com/problems/house-robber-iii/

---

이진 트리로 구성된 집들의 구조가 있다. 도둑은 집들에 침입해 도둑질을 하려고 하는데 연결된 집을 동시에 털면 경찰에 연락이 간다.

경찰에 연락이 가지 않게 집들을 도둑질하려고 할 때, 훔칠수 있는 최대 금액을 구해라.

---

memoization을 위해 TreeNode*을 키 값으로 하고 해당 노드를 헤드노드로 한 서브트리에서 조건을 만족하며 훔칠 수 있는 최대 금액을 저장한다.

 

탐색 중인 노드를 훔쳤다면 왼쪽, 오른쪽 자식 노드들은 훔치면 안되므로 왼쪽 자식 노드의 자식 노드들, 오른쪽 자식 노드의 자식 노드들을 다시 헤드 트리로 하여 훔칠 수 있는 최대 금액들의 합이 정답이 될 수 있다. 

또한 탐색 중인 노드를 훔치지 않고 왼쪽, 오른쪽 자식 노드들을 다시 헤드 트리로 하여 훔칠 수 있는 최대 금액들의 합 또한 정답이 될 수 있다. 

정답이 가능한 두 가지 경우 중 최대값이 정답이 된다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/337.%20House%20Robber%20III.cpp