algorithm - 计算二叉树中每个节点的子树大小的运行时间是多少

Question

当我在做二叉树练习时，有一个问题让我很困惑:

给定一棵具有 n 个节点的二叉树(通过指向其根的指针)。令 size(n) 表示以节点 n 为根的子树中的节点数。为树的每个节点 n 计算 size(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
        }
    }
}