質問: getHeight(root.right) - getHeight(root.left); if(Math.abs(heightDiff) > 1) { return false; } else { return isBlanced(root.left) && isBlanced(root.right); } } ``` このようにすればうまくいきますが、それほど効率的ではありません。各ノードで他の部分木を再帰していますが、これはgetHeightが同じノードで繰り返し呼び出されていることになります。ですので、このアルゴリズムはO(N^2)の計算量になってしまいます。 「各ノードで他の部分木を再帰していますが、これはgetHeightが同じノードで繰り返し呼び出されていることになります。」 この文章がイマイチ理解できません。 ここでいう他の部分木とはrightとleftで指定される子ノードのことで間違い無いですよね? getHeightが同じノードで繰り返し、呼び出されるとは一体どのような意味なのでしょうか? お分かりの方、回答お願いします。 補足です。 みなさま、回答ありがとうございます。 大元のノードで高さを算出した後、その高さが1以下だった場合、その子ノードで再び高さが算出されるので、非効率なわけですね。 ここまでは理解できたのですが、なぜO(N^2)になるのでしょうか? 要素数が2倍になると、計算量が4倍になるのはなぜなのでしょうか?
回答: # この種の質問はタグ「アルゴリズム」を入れるのがいいと思います。 単純例の効率が悪いのはswordoneさんのご説明の通りです。 効率よくやる方法は、という問題になると思いますが、もしわからなかったら以下をヒントにどうぞ。 * 深さ優先探索ですべての葉を巡ります。 * 深さmax, 深さminというのを保持しておくことにし、それぞれの葉をたどったときにその深さでmin,maxを更新します。 * max-minが1を越えた時点で計算を打ち切り、falseを返します。 * 深さ優先探索を無事終えられたらtrueを返します。 これならO(N)。 最初の葉を見つけるまでの間min,maxはどんな値にしておくかなどいくつか工夫しどころがあります。