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
        }
    }
}

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;
}