用树和递归求时间复杂度

发布于 2024-12-12 05:31:12 字数 232 浏览 0 评论 0原文

我认为这是 O(n) 对吗？我真的不擅长递归。有人可以向我确认或解释一下吗？

Counter(a)
    if hasLeft(a)
        return Counter(left(a) + Counter (right(a))
    else
        return 1

基本上，如果树中没有左节点，则返回 0。如果有左注释，则返回 1。

谢谢！

原文

Am I right in thinking this is O(n)? I'm really bad at recursion. Could someone please confirm, or explain to me?

Counter(a)
    if hasLeft(a)
        return Counter(left(a) + Counter (right(a))
    else
        return 1

Basically, if there isn't a left node in the tree, it returns 0. If there are left notes, it returns 1.

Thanks!

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

岁月静好 2024-12-19 05:31:12

如果它是（二叉）树，因为图中没有任何循环，它最多只检查每个节点一次，所以它是O(n)。

回复收藏 0 原文

纸短情长 2024-12-19 05:31:12

您的代码不执行广告中的操作。你说如果有左节点则返回 1，如果没有左节点则返回 0。但你的代码是：

Counter(a)
    if hasLeft(a)
        return Counter(left(a)) + Counter(right(a))
    else
        return 1

如果根处没有左节点，则返回 1，但它不会检查树的其余部分。此代码不会检查整个树，而是会在没有左节点的第一层停止。

你到底想做什么？

Your code doesn't do what's advertised. You said you want it to return 1 if there is a left node, and 0 if there is not a left node. But your code is:

Counter(a)
    if hasLeft(a)
        return Counter(left(a)) + Counter(right(a))
    else
        return 1

This returns 1 if there is no left node at the root, but it doesn't check the rest of the tree. This code will not examine the entire tree, but rather will stop at the first level that has no left node.

What are you really trying to do?

回复收藏 0 原文

~没有更多了~