在二叉搜索樹中打印最大深度

我想獲得二叉搜索樹的最大深度，但是我相信樹計算錯誤。在二叉搜索樹中打印最大深度

我的代碼：

def BST_maxdepth(root): 
     curdepth = [1] 
     maxdepth = [1] 
     if root is None: 
      return -1 
     else: 
      curdepth[0] = 1 
      maxdepth[0] = 1 
      if root.left is not None or root.right is not None: 
       curdepth[0] += 1 
       if curdepth[0] > maxdepth[0]: 
        maxdepth[0] = curdepth[0] 
       BST_maxdepth(root.left) 
       BST_maxdepth(root.right) 
     return maxdepth[0]

類& BST：

class Node: 
    def __init__(self,value): 
     self.right = None 
     self.left = None 
     self.value = value 


def BST_Insert(root, node):  # root --> root of tree or subtree! 
    if root.value is None: 
     root = node    # beginning of tree 
    else: 
     if root.value > node.value:  # go to left 
      if root.left is None: 
       root.left = node 
      else: 
       BST_Insert(root.left, node) 

     if root.value < node.value: # go to right 
      if root.right is None: 
       root.right = node 
      else: 
       BST_Insert(root.right, node)

測試：

r = Node(8) 


a = Node(5) 
b = Node(2) 
c = Node(1) 
d = Node(3) 
e = Node(7)

輸出：

2

預期輸出：

4

來源

2013-10-04 Liondancer

是不是你的深度實際上應該是4？ – Michael

對不起，我使用了錯誤的樣本數據，我正在測試，但在這種情況下，你是對的 – Liondancer

爲何不像......

def BST_maxdepth(root, depth=0): 
    if root is None: 
     return depth 
    return max(BST_maxdepth(root.left, depth+1), 
       BST_maxdepth(root.right, depth+1))

來源

2013-10-04 22:36:01

你沒有更新一次maxdepth更多。也許是這樣的：

left_depth = BST_maxdepth(root.left) 
right_depth = BST_maxdepth(root.right) 
maxdepth[0] = max(left_depth, right_depth) + 1

來源

2013-10-04 22:30:58 Michael

，你遞歸，而且他們不是全球性的你不能隨身攜帶curdepth和maxdepth。在每次致電BST_maxdepth時，您聲明新的curdepth和maxdepth。

這意味着無論你的樹有多深，maxdepth將只有2（或者如果根沒有孩子，則爲1）。

您可以嘗試使用累加器，或從每次遞歸調用中返回一個值並以此方式構建maxdepth。

來源

2013-10-04 22:31:34 dckrooney

是的，你是對的！對不起，我將一些我的c/C++編程習慣帶入python，並聲明兩者之間的變量不同，所以我傾向於混淆 – Liondancer

您的maxdepth從每個遞歸步驟都沒有傳遞給父步驟。

的信息從

BST_maxdepth(root.left) 
BST_maxdepth(root.right)

需要返回到父。

您重新實例化他們在搜索的每個級別：

curdepth = [1] 
maxdepth = [1]

來源

2013-10-04 22:34:30 DanGar

在二叉搜索樹中打印最大深度

回答

相關問題