查找树木和递归的时间复杂度

我是否认为这是O（n）？递归我真的很糟糕。有人可以确认，或向我解释？查找树木和递归的时间复杂度

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

基本上，如果没有在树中的左节点，则返回0。如果有剩下的笔记，它返回1

谢谢！

2011-10-26 Kris

如果您的意图是基于没有左节点/左节点确实返回0或1，您可以非常容易地创建一个O（1）例程并且不需要递归。除此之外，你真的不清楚你想要完成什么，但感觉就像你的代码示例有缺陷（如果hasLeft（a）....基于左（a）递归...当你已经确定没有左分支 – mah

对不起 - 我修正了它，我并不是这样的！我只是试图了解递归和时间复杂度，使用这个特定的代码 – Kris

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

2011-10-26 19:32:31

我只是减少了算法，忘记了删除h，我将它编辑出来，我以为是O（n） - 感谢您的确认+解释！ – Kris

@Kris，如果这是您的答案，请将答案左侧的复选框切换为绿色。 –

完成！谢谢 – Kris

你的代码不会做广告。你说你想让它返回1，如果有一个左节点，如果没有左节点，则返回0。但是你的代码是：

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

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

你真的想做什么？

2011-10-26 20:49:24

他的问题是关于运行时间，而不是代码是否正确，这个答案可以是一个评论。null checking，... are another notes。 –

@Saeed：我明白，但这很难给予th运行时间不适用的代码。 –

你可以假设这是一个伪代码，它可以在你没有推荐的情况下工作（但是他应该添加空的检查），但可能并不是他想要的，但它是一种算法并且有运行时间。 –

回答