1 
int cntHeight(TreeNode *root) {
    if(root == NULL) return 0;
    int l = cntHeight(root->left);
    int r = cntHeight(root->right);
    if(l < 0 || r < 0 || abs(l-r) > 1) return -1;
    else  return max(l, r) + 1;
}

bool isBalanced(TreeNode *root) {
    return cntHeight(root) >= 0;
}

二分木がバランスが取れているかどうかを確認するために、Cでこのソリューションを見つけました。ただし、このアルゴリズムが完全にどのように機能するかを視覚化するのは非常に困難です。そのため、私が確信していない点が 2 つあります。

  1. アルゴリズムは、ツリーの両側だけでなく、途中で再帰しますか?
  2. max(1, r)のみが呼び出されていることに気付きminました。 も検索する必要はありませんか?

さらに、このようなアルゴリズムを開発するにはどうすればよいでしょうか? このような解決策を思いつく方法がわかりません..

4

2 に答える 2

1

cntHeight 関数で魔法が起こります。ツリーの一部を引数として取り、その部分が空の場合は 0 を返し、バランスが取れていない場合は -1 を返し、それ以外の場合はバランスが取れている場合はその深さを返します。

これを行うには、まず自分自身を呼び出して、両方のサブツリー (左と右) の深さを取得します。これらのサブツリーの 1 つが不均衡である場合、ツリー全体が不均衡であるため、すぐに -1 を返します。サブツリーの 1 つが他のサブツリーよりも 2 深い場合、ツリーもバランスが取れていないため、-1 が返されます (これがabs(l-r) > 1チェック対象です)。

最後の行で、関数は渡されたツリーの深さを計算します。これは、ルート ノードのより深いサブツリーの深さ (したがってmax) + 1 です。

このようなアルゴリズムを開発するための主な要素は経験だと思います。見たアルゴリズムが多ければ多いほど、得られる利用可能なメソッドに対する感覚が増します。

于 2013-09-13T03:42:30.433 に答える