문제

https://leetcode.com/problems/balanced-binary-tree/

문제 접근 및 풀이

쉽다고 생각했는데 생각보다 애먹었다.
처음에는 그냥 root를 기준으로 오른쪽과 왼쪽 깊이의 차이가 1이 넘게 되면 false를 반환했는데, 이렇게 하니까

이 반례가 나왔다.. 오른쪽도 깊이가 3, 왼쪽도 깊이가 3이다. 하지만 height-balanced binary tree가 아님..
그냥 탐색을 하면서 깊이가 1이상 차이나면 걸러주는 식으로 해야하는데 그 표현을 어떻게 할지 막막했다.
false를 return하면 깊이 값은 어떻게 return 하지? 숫자와 boolean을 제각각 조건마다 다르게 return하면 int를 return하는 함수가 아니고..
그래서 -1을 두어서 max에 걸리지도 않고 아예 나올 수 없는 숫자이므로 -1을 가지고 처리했다.

결과

const searchDepth = (node, depth) => {
  if (node === null) return depth;
  depth++;

  const leftDepth = searchDepth(node.left, depth);
  const rightDepth = searchDepth(node.right, depth);

  if (leftDepth === -1 || rightDepth === -1) return -1;
  if (Math.abs(leftDepth - rightDepth) > 1) return -1;

  const max = Math.max(leftDepth, rightDepth);
  return max;
};

const isBalanced = (root) => {
  if (root === null) return true;
  return searchDepth(root, 0) !== -1;
};

사담

아직도 재귀에 대한 이해가 부족