Binary Tree에서 같은 숫자로만 구성된 subtree개수 구하기

1. 끝단은 무조건 같은 숫자로 구성된 subtree가 된다.

 

2. 문제는 어떤 변수를 전역으로 둘 것인가이다.

  2-1 같은 숫자로 구성된 subtree를 찾으려면 현재 어떤 숫자인지를 우선 가지고 있어야 하고

  2-2 현 위치에서 아래의 트리가 같은 숫자로 구성되어 있는지 상태값을 가져야 한다.

  2-3 현재까지 몇개의 서브트리를 찾았는지도 알아야 한다.

 

3. 쉽게 빠지는 유혹은 반환값을 서브트리 판단으로 1을 올리거나 안올리거나를 하고 싶은 유혹이 든다. 그렇게 되면 현 시점에 하위 트리에 대한 정보를 전역으로 보관해야 한다.

   3-1 해결이 힘들다.

 

4. 결론적으로 말하면 재귀적으로 현재 하위 트리가 같은 숫자로 구성된 서브트리인지 true, false를 반환하고, 서브트리 숫자를 전역으로 가지는 것이 효율적이다. 

  4-1 자식이 규칙에 해당하는 서브트리인지 알면 본인 역시 규칙에 해당하는지 알 수 있고 카운트를 올릴지 판단할 수 있다.

 

5. 중요한 현재 시점에서 자식 노드로 부터 어떤 정보를 가져야 전체 문제를 풀수 있는지 고민하는 것이 중요하다.