algorithm - バイナリ ツリーのすべてのノードのサブツリーのサイズを計算する実行時間は?

Question

バイナリ ツリーの演習を行っていたとき、私を混乱させる 1 つの質問がありました。

n 個のノードを持つ (ルートへのポインターを介して) 二分木が与えられます。size(n) は、ノード n をルートとするサブツリー内のノードの数を示します。木の各ノード n のサイズ (n) を計算するのに必要かつ十分な時間は?

上の質問のヒントを誰か教えてください。前もって感謝します！

Answer 1

@user1952500アルゴリズムにはいくつかのエラーがあります。

1. void関数内で0を返します
2. 初期値を指定せずにnode->numに追加します
3. サブツリーサイズを計算するために子ノードをトラバースしません

したがって、修正バージョンは次のようになります。

struct tree
{
    int num;
    struct tree *l;
    struct tree *r;
};

void sizeofnode(tree *node)
{
    if (node) { 
        node->num = 1; // Our size

        if (node->l) {
            sizeofnode(node->l);       // Calculates size of left subtree
            node->num += node->l->num; // Adds size of left subtree
        }

        if (node->r) {
            sizeofnode(node->r);       // Calculates size of right subtree
            node->num += node->r->num; // Adds size of right subtree
        }
    }
}

Answer 2

n をルートとするサブツリーのサイズを取得するには、各サブツリーのサイズを再帰的に取得する必要があります。これは本質的に、ツリーの各ノードにアクセスすることになることを意味します。

したがって、時間の複雑さは O(n) だと思います。

Answer 3

O(n) スペースを使用できる場合は、O(n) ソリューションを使用できます。

ここで「num」は O(n) スペースの理由です。

struct tree
{
    int num;
    struct tree *l;
    struct tree *r;
};

void sizeofnode(tree *node)
{
    if (!node) {
        return;
    }
    node->num = 0;

    if (node->l) {
        node->num += node->l->num; // size of left subtree
    }

    if (node->r) {
        node->num += node->r->num; // size of right subtree
    }

    node->num ++; // this is to add the size of the root of the subtree

    return;
}