二叉樹的高度

Question

我想實現一個遞歸方法來計算二叉樹的高度。這裏是「高度」 -code：

def height(self): 
    if self.root==None: 
     return 0 
    return max(height(self.root.left), height(self.root.right))+1 

當我嘗試調用函數，我得到以下錯誤信息：

NameError: name 'height' is not defined 

是否有人看到這個問題？

Answer 1

這是您的班級的一種方法，因此您必須從實例（self）或班級本身調用它。儘管它不會像您想象的那樣工作，除非您將其定義爲staticmethod或更改呼叫，例如

def height(self): 
    return 1 + max(self.left.height() if self.left is not None else 0, 
        self.right.height() if self.right is not None else 0) 

或

@staticmethod 
def height(self): 
    return 1 + max(self.height(self.left) if self.left is not None else 0, 
        self.height(self.right) if self.right is not None else 0) 

請注意，你不應該使用==與None比較（榮譽給timgeb）。你也必須檢查是否存在子節點。而你的算法不起作用，所以我稍微改變了它。

例子：

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

    def height(self): 
     return 1 + max(self.left.height() if self.left is not None else 0, 
         self.right.height() if self.right is not None else 0) 


# Create a binary tree of height 4 using the binary-heap property 
tree = [Node() for _ in range(10)] 
root = tree[0] 

for i in range(len(tree)): 
    l_child_idx, r_child_idx = (i + 1) * 2 - 1, (i + 1) * 2 
    root_idx = (i + 1) // 2 
    if root_idx: 
     tree[i].root = tree[root_idx] 
    if l_child_idx < len(tree): 
     tree[i].left = tree[l_child_idx] 
    if r_child_idx < len(tree): 
     tree[i].right = tree[r_child_idx] 

print(root.height()) # -> 4 

Answer 2

我不知道你是如何定義你的二叉樹。但是在樹節點上，通常只有一個根和多個兒子。我覺得這種方法會導致無限循環。 self.root.left和self.root.right正是我的兄弟和我...

在這裏，您可能必須從實例self.root.left和self.root.right中調用該方法，而無需額外參數：

def height(self): 
    if self.root==None: 
     return 0 
    return max(self.root.left.height(), self.root.right.height())+1