Day-80: 完全二分木のノード数を数える

Other
Day-80: 完全二分木のノード数を数える

Day-80: 完全二分木のノード数を数える

このリポジトリは「完全二分木（complete binary tree）のノード数を数える」アルゴリズム課題のワークフォルダです。LeetCode風の問題文を含むREADMEと、実装らしきソース（src.txt）のみから成る非常にシンプルなリポジトリで、目標は O(n) より速いアルゴリズムの設計です。完全二分木の特性（最下層が左寄せであること）を利用し、高速にノード数を求める手法（高さ判定と二分探索／再帰的判定で O((log n)^2) など）を想定した学習・備忘録的な内容になっています。

https://github.com/annu-creator24t/Day-80-Count-Complete-Tree

概要

このリポジトリは「Day-80-Count-Complete-Tree」というタイトルのもと、完全二分木のノード数を効率的に数える問題に取り組むための最小限のプロジェクトです。READMEには問題の説明と例が記載され、実装ファイル（src.txt）が含まれています。目標は全ノードを走査する O(n) より速いアルゴリズムの設計で、完全二分木の高さや部分木が完全かどうかを利用して高速化する典型的な手法（高さ判定＋二分探索または再帰判定）を想定しています。実装言語は明示されておらず、ファイル数も少ないため学習目的のサンプル集や解答メモとして使いやすい構成です。

GitHub

リポジトリの統計情報

  • スター数: 1
  • フォーク数: 0
  • ウォッチャー数: 1
  • コミット数: 3
  • ファイル数: 2
  • メインの言語: 未指定

主な特徴

  • 完全二分木のノード数を O(n) 未満で求めるアルゴリズムの課題を扱う。
  • README に問題定義と簡単な入力例が記載されている。
  • 実装ファイルは1つ（src.txt）で、学習用やメモ用途に最適。
  • リポジトリは軽量で取り回しが簡単。拡張や言語差分の追加もしやすい。

技術的なポイント

完全二分木に特化したノード数カウントのキーは「完全二分木の構造的性質」を利用する点です。完全二分木では最下層を除く各レベルが完全に埋まっているため、部分木が「完全（perfect）」かどうかを判定できれば、その部分木のノード数は 2^h - 1（h は高さ）で即座に得られます。よく使われる高速アルゴリズムは次の通りです。

  1. 左端・右端の深さを計測：あるノードから左に辿ったときの深さと右に辿ったときの深さが等しければ、その部分木は完全（perfect）でありノード数を O(1) で計算可能。異なれば左右どちらかの部分木が perfect であることを利用して再帰的に処理する。これにより最悪計算量は O((log n)^2) になる（高さを求めるコストが O(log n)、これを高さ回数分だけ行うため）。

  2. 二分探索による最下層の存在検査：木の高さ h を求め、最下層に存在するノードのインデックスを 0..2^h-1 とみなして二分探索で存在判定（経路をビット列で表し、左/右移動を辿る）を行う手法。各判定は O(log n)、探索は O(log n) 回なので全体で O((log n)^2) に収まる。

実装上の注意点：

  • 木の高さ取得はルートから左へ進むだけで良く O(log n)。
  • 再帰深度やビット操作を用いると効率的かつ簡潔に書ける（Python, Java, C++ どれでも採用可能）。
  • 空の木（root = []）やノードが極端に少ない場合のエッジケースを明示的に扱うこと。
  • ラージケースでは再帰/反復のどちらが適切か検討（言語ごとのスタック上限を考慮）。

このリポジトリ自体は最小構成ながら、上述のアルゴリズム群を学ぶための良い出発点です。実装を言語別に増やしたり、ベンチマークを追加して O(n) との比較評価を行うことで教育資源としての価値を高められます。

プロジェクトの構成

主要なファイルとディレクトリ：

  • README.md: file
  • src.txt: file

まとめ

完全二分木の特性を使えば、全走査を避けて高速にノード数を求められます。

リポジトリ情報：

READMEの抜粋：

Day-80-Count-Complete-Tree

Given the root of a complete binary tree, return the number of the nodes in the tree. According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1: Input: root = [1,2,3,4,5,6] Output: 6

Example 2: Input: root = [] O…