algorithm - ツリー内の特定のノードの前にある葉を数える方法は?

Question

そのツリー内の特定の要素の前に見つかった葉の数を返す関数をどのように実装しますか? ツリーを左から右に読んでいると仮定しますか?

私はそれをするために離れていましたが、それはあまり簡単ではなく、例外メカニズムを使用しています.それを行うためのエレガントな方法があると思いますか?

Answer 1

おそらく、ツリーを dfs し、葉を数え、すべてのノードに保存することができます。お気に入り

int count;

void dfs(int x){
    dfs(x->left);
    leafBefore[x] = count;
    if (x is leaf) count += 1;
    dfs(x->right);
}

count = 0;
dfs(root);