「二分木が平衡かどうか調べる関数を実装してください。平衡木とは、どのノードの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倍になるのはなぜなのでしょうか?
回答2件
あなたの回答
tips
プレビュー