[LeetCode] 222. Count Complete Tree Nodes

😎풀이

1. 좌측 서브트리 높이를 구한다.
2. 우측 서브트리 높이를 구한다.
3. 좌 우 서브트리 높이가 같은지 비교한다.
   3-1. 같다면, 2의 h제곱 - 1을 통해 전체 노드의 수를 바로 구한다.
   3-2. 다르다면, 재귀적으로 현재 노드 + 좌측 노드(재귀) + 우측 노드(재귀)를 통해 총 노드의 수를 구한다.

function countNodes(root: TreeNode | null): number {
  if (!root) return 0;

  // 왼쪽 서브트리의 높이 계산
  let leftHeight = 0;
  let leftNode = root;
  while (leftNode) {
    leftHeight++;
    leftNode = leftNode.left;
  }

  // 오른쪽 서브트리의 높이 계산
  let rightHeight = 0;
  let rightNode = root;
  while (rightNode) {
    rightHeight++;
    rightNode = rightNode.right;
  }

  // 만약 왼쪽 높이와 오른쪽 높이가 같다면, 완전 이진 트리이므로 노드 수를 바로 계산
  // 매 층마다 자식노드를 2개씩 갖으므로 2의 h제곱
  if (leftHeight === rightHeight) {
    return (1 << leftHeight) - 1; // 2^h - 1
  }

  // 그렇지 않다면, 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색
  return 1 + countNodes(root.left) + countNodes(root.right);
}