针对二叉搜索树的两个单独的getHeight算法的运行时间

对于二叉搜索树（不一定是平衡BST），我有两个独立的getHeight（）方法实现，一个是迭代的，一个是递归的。这里的迭代之一：针对二叉搜索树的两个单独的getHeight算法的运行时间

def height(root): #iterative approach, uses a stack for a depth first search 
    max_height = 0 
    myStack = [root] 
    currentNode = None 
    root.level = True 

    while len(myStack) != 0: 
     currentNode = myStack[-1] 
     if currentNode.left is not None and currentNode.left.level is not True: 
      myStack.append(currentNode.left) 
      currentNode.left.level = True 
      continue 
     if currentNode.right is not None and currentNode.right.level is not True: 
      myStack.append(currentNode.right) 
      currentNode.right.level = True 
      continue 
     elif (currentNode.left is None or currentNode.left.level is True) and (currentNode.right is None or currentNode.right.level is True): 
      height = len(myStack) - 1 
      if height > max_height: 
       max_height = height 
      myStack.pop() 
return max_height

和这里的递归方法：

def recurseHeight(root): 
    add = 0 
    l, r = 0, 0 
    if root.left is not None: 
     l = 1 + recurseHeight(root.left) 
    if root.right is not None: 
     r = 1 + recurseHeight(root.right) 

    return l if l > r else r

所以，我从空间的角度看复杂知道，递归算法是更好的。然而，从我的理解来看，迭代算法的运行时间是O（n）（因为它必须搜索所有n个节点，并且不会停止到该点），但是我想知道递归算法的运行时间是什么。我知道我将不得不使用主定理，而我的一部分人认为它也会是O（n），因为无论如何我都必须访问所有节点，但我不确定。任何人都可以帮助找到递归算法的运行时间？

（侧面说明，我在做这个练习面试 - 如果任何人有很好的问题/学习资源，不要犹豫，说他们响亮而自豪:)）

来源

2017-07-17 dgamz

而不是猜测，你可以简单地分析两种方法，他们的内存和CPU使用率。请参阅https://stackoverflow.com/a/43629424/1656850。此外，欢迎访问本网站：您可能想阅读[帮助/话题]，[问]和[mcve]。 – boardrider

至于你说的究竟是O（n），因为你总是访问树中的每个节点，只访问每一个节点，这意味着你需要O（n）的工作递归版本

来源

2017-07-17 22:01:56 m7mdbadawy

针对二叉搜索树的两个单独的getHeight算法的运行时间

回答

相关问题