Python: вычислить максимальную высоту дерева с несколькими детьми

Question

def __init__(self,label=None):
    self.label = label
    self.leftMostChild = None
    self.RightSibling = None


def height(self):
    if self.leftMostChild == None and self.RightSibling == None:
        return 0
    else:
        if self.leftMostChild:
            return self.leftMostChild.height() + 1

        if self.RightSibling:
            return self.RightSibling.height()

Очевидно, высота отключена на 1. Когда дерево с высотой 3 создается, 2 возвращается после вызова функции height. Я не уверен, где я сделал неправильно в этой функции.

Любая помощь будет оценена.

Answer 1

Возврат приводит к немедленному завершению функции. Это означает, что если узел имеет как самого левого дочернего, так и правого родного брата, правый родной брат никогда не будет оцениваться. Вот функция только с одним возвратом для каждой ветви if/else.

def height(self):
    if self.leftMostChild == None and self.RightSibling == None:
        return 0
    else:
        leftHeight = rightHeight = 0
        if self.leftMostChild:
            leftHeight =  self.leftMostChild.height() + 1

        if self.RightSibling:
            rightHeight = self.RightSibling.height()
        return max(leftHeight, rightHeight)

Это может быть дополнительно упрощено до:

def height(self):
    leftHeight = rightHeight = 0
    if self.leftMostChild:
        leftHeight =  self.leftMostChild.height() + 1
    if self.RightSibling:
        rightHeight = self.RightSibling.height()
    return max(leftHeight, rightHeight)