以下のメソッドは二分木が平衡かどうか調べるメソッドです。
「二分木が平衡かどうか調べる関数を実装してください。平衡木とは、どのノードの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)の計算量になってしまいます。」
同じ部分が繰り返し数えられるので、非効率なのはわかるのですが、なぜO(N^2)になるのでしょうか?
考えてみたのですが、わかりませんでした。
お分かりの方、回答お願いします。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2016/09/04 05:51
2016/09/04 13:03
退会済みユーザー
2016/09/04 14:22
2016/09/04 14:37
2016/09/04 14:57
退会済みユーザー
2016/09/05 13:11