[Question] isBalancedTree?

문제: 인자로 들어오는 Binary Tree는 Balanced인가 아닌가를 구분하는 함수를 만들어라.

문제를 풀기 앞서 몇 가지 개념 정리를 해야 할 것 같다. Binary 트리라 불리는 이진트리 데이터 구조는 무엇인가? 이진 트리는 0개 혹은 1개, 2개의 자식노드를 같는 트리를 말한다. 그럼 해당 데이터 구조가 균형잡히다, 라는 것은 무슨 뜻일까? Balanced하다 하는 것은 자신의 자식노드의 깊이의 차이가 1보다 많아서는 안될 때 균평 잡힌 이진트리이다. 라고 말한다.

Screen Shot 2016-01-07 at 11.35.58 AM

위 예제는 균형잡힌 이진트리이다. 왜냐하면 모든 노드의 자식노드들의 깊이 차이가 1을 넘어 서는 것이 없기 때문이다.

Screen Shot 2016-01-07 at 11.36.09 AM

위 예제는 균형잡힌 이진트리가 아니이다. 왜냐하면 1의 자식들의 깊이의 차이가 1보다 큰 2이기 때문이다.

그렇다면 균형잡힌 이진트리를 찾기 위해서 어떻게해야 할 것인가? 고민해보자.

주먹구구식으로 먼저 생각을 해보자. 모든 노드의 자식의 차이를 구하고 그의 차이가 1 보다 큰 것이 나오면 false를 그 이외의 것들은 True를 반환하면 된다.

아래 답을 보기 전에 먼저 손수 풀어보자. 효율적인 함수를 짜기 위해서는 고민을 좀 해봐야 할 것이다. 왜냐하면 노드의 깊이도 구해야 할 것이고 Bool 값도 반환하고 싶을 것이기 때문이다.

이 문제의 팁은 -1를 통해 깊이 계산과 동시에 불균형를 표시하는 것이다.

  1. - (BOOL)isBalanced:(Node *)rootNode{
  2.     if([self getNodeDepth:rootNode] == -1){
  3.         return NO;
  4.     }
  5.     return YES;
  6. }
  7.  
  8. - (NSInteger)getNodeDepth:(Node *)node{
  9.     if(node == nil){
  10.         return 0;
  11.     }
  12.  
  13.     NSInteger leftDepth = [self getNodeDepth:node.left];
  14.     if(leftDepth == -1){
  15.         return -1;
  16.     }
  17.  
  18.     NSInteger rightDepth = [self getNodeDepth:node.right];
  19.     if(rightDepth == -1){
  20.         return -1;
  21.     }
  22.  
  23.     NSInteger depthDiff = Abs(leftDepth – rightDepth);
  24.     if(depthDiff > 1){
  25.         return -1;
  26.     }
  27.  
  28.     return Max(leftDepth, rightDepth) + 1;
  29. }