バイナリ検索ツリーの2つの別々のgetHeightアルゴリズムの実行時間

Question

バイナリ検索ツリーのgetHeight（）メソッドを2つ別々に実装しています（必ずしもバランスBSTでなくてもかまいません）。ここでは、反復一つだ：

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）でもあると考えています。誰でも再帰アルゴリズムのランタイムを見つけるのに役立つでしょうか？

（サイドノート、私はインタビューのために練習するためにこれをやっている - 誰でもいい問題/学習リソースを持っている場合は、:)大声で、誇りに思ってそれを言うことを躊躇しない）

Answer 1

あなたは正確に言っていると、それはですあなたがいつもツリーのすべてのノードにアクセスし、それぞれを1回だけ訪問するので、再帰的バージョンの仕事のO（n）が必要です。