JavaScript로 이진트리 깊이-균형 확인하는 함수 구현하기
문제분석
이진트리가 인자로 들어올 때, 이 트리가 깊이-균형 인지 아닌지 판단하는 함수를 구현하시오
깊이-균형 이진 트리는 다음과 같이 정의된다.
왼쪽과, 오른쪽 자식트리들의 모든 노드의 깊이에서 차이가 1을 초과하지 않는 이진트리.
돌파구
역시나, 이진트리를 다룰 때에는 재귀가 필요하다. 물론, 앞서 DFS를 구현 할 때 처럼 배열과 함께 iterable 하게 모든트리를 방문해도 되지만, 주어진 문제의 구현을 위해서는 재귀로 DFS를 구현하는 것이 더 이해하기가 쉬웠다.
이 문제의 돌파구는 바로, 재귀로 DFS를 구현하고, 그 안에 들어가는 조건문이다. 위의 문제에서 깊이-균형이 되는지 아닌지를 판단하는 조건문이 DFS 함수 안에 들어가면 된다. 왼쪽과, 오른쪽의 깊이의 차가 1을 넘게 되면 그 트리는 깊이-균형 트리가 아닌 것이다. 이 조건문을 재귀 함수 안에 구현하는 것이 이 문제의 돌파구였다.
구현
먼저 dfs로 트리의 최대 깊이를 return 하는 함수를 구현한다.
위의 dfs 함수 안에서, 트리가 깊이-균형인지 아닌지 left, right 의 차이를 비교하면 된다.
즉, Math.abs(left-right) > 1 가 참이면, 이 트리는 깊이-균형인 트리가 아니다. 이 조건을 성립할 때, 함수의 구현상 나올 수 없는 값을 주어서 조건을 처리해 주면된다. 나는 이 때, -1을 return 하게 했다.
중요한것은, 저기 아래에 있는 자식트리가 깊이-균형이 -1 을 리턴하게 되면, 콜스택을 타고올라가서 최종적으로 -1을 return 하게 해야한다. 이 제어를 하기 위해서는 left === -1 || right === -1 인지 체크를 해 주어야 한다.
이 조건문을 하나의 조건문으로 구성하면 다음과 같이 된다. if(left === -1 || right === -1 || Math.abs(left-right) > 1) return -1
