質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

2回答

1828閲覧

二分木が平衡かどうか調べる関数

退会済みユーザー

退会済みユーザー

総合スコア0

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2016/08/31 02:44

編集2016/08/31 05:56

「二分木が平衡かどうか調べる関数を実装してください。平衡木とは、どのノードの2つの部分木も、その高さの差が1以下であると定義します。」

(解答例)
単純に木全体を再帰し、各ノードに対して部分木の高さを計算すれば良い。

Java

1public static int getHeight(TreeNode root) { 2 if(root == null) return 0; //基本ケース 3 return Math.max(getHeight(root.left), 4 getHeight(root.right)) +1; 5 } 6 7 public static boolean isBlanced(TreeNode root) { 8 if(root == null) return true; //基本ケース 9 10 int heightDiff = getHeight(root.right) - getHeight(root.left); 11 if(Math.abs(heightDiff) > 1) { 12 return false; 13 } else { 14 return isBlanced(root.left) && isBlanced(root.right); 15 } 16 }

このようにすればうまくいきますが、それほど効率的ではありません。各ノードで他の部分木を再帰していますが、これはgetHeightが同じノードで繰り返し呼び出されていることになります。ですので、このアルゴリズムはO(N^2)の計算量になってしまいます。

「各ノードで他の部分木を再帰していますが、これはgetHeightが同じノードで繰り返し呼び出されていることになります。」
この文章がイマイチ理解できません。
ここでいう他の部分木とはrightとleftで指定される子ノードのことで間違い無いですよね?
getHeightが同じノードで繰り返し、呼び出されるとは一体どのような意味なのでしょうか?

お分かりの方、回答お願いします。

補足です。
みなさま、回答ありがとうございます。
大元のノードで高さを算出した後、その高さが1以下だった場合、その子ノードで再び高さが算出されるので、非効率なわけですね。
ここまでは理解できたのですが、なぜO(N^2)になるのでしょうか?
要素数が2倍になると、計算量が4倍になるのはなぜなのでしょうか?

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2016/08/31 02:58 編集

ん・w・ root.left.right == root で無限ループなんじゃ
guest

回答2

0

# この種の質問はタグ「アルゴリズム」を入れるのがいいと思います。

単純例の効率が悪いのはswordoneさんのご説明の通りです。
効率よくやる方法は、という問題になると思いますが、もしわからなかったら以下をヒントにどうぞ。

  • 深さ優先探索ですべての葉を巡ります。
  • 深さmax, 深さminというのを保持しておくことにし、それぞれの葉をたどったときにその深さでmin,maxを更新します。
  • max-minが1を越えた時点で計算を打ち切り、falseを返します。
  • 深さ優先探索を無事終えられたらtrueを返します。

これならO(N)。
最初の葉を見つけるまでの間min,maxはどんな値にしておくかなどいくつか工夫しどころがあります。

投稿2016/08/31 03:12

yuba

総合スコア5568

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

java

1// 2 public static int getHeight(TreeNode root) { 3 if(root == null) return 0; //基本ケース 4 return Math.max(getHeight(root.left), 5 getHeight(root.right)) +1; 6 }

部分木の高さの算出は、単純に二分木の下に伸びるノード数を数えているものです。

java

1int heightDiff = getHeight(root.right) - getHeight(root.left);

まず左右の部分木の高さをここで求め、差を取っています。

java

1// 2 if(Math.abs(heightDiff) > 1) { 3 return false; 4 } else { 5 return isBlanced(root.left) && isBlanced(root.right); 6 }

この差が2以上であればその時点で条件に反するためfalseを返しますが、1以下の場合は「各部分木が平衡かどうか」を調べるために再帰をしています。この再帰で、左右の各子ノードからの高さを計算することになります。つまり、大本のノードから一番下までノードを数えたのに、それをまた左右のノードを出発点に数え直すことになるのです。

投稿2016/08/31 02:55

swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問