анализируется BST высота сбалансирована - PullRequest
Новая
       6

анализируется BST высота сбалансирована

0 голосов
/ 29 мая 2018

Я искал код для проверки, является ли BST сбалансированным по высоте, и у меня возник вопрос по поводу понимания следующего кода. 

def is_balanced(cur_node) :
        if (not cur_node) :
            height = 0
            return True, height

        is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
        is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)

        #To get the height of the current node, we find the maximum of the  
        #left subtree height and the right subtree height and add 1 to it
        height = max(left_height, right_height) + 1

        if (not is_left_balanced or not is_right_balanced):
            return False, height

        #If the difference between height of left subtree and height of
        #right subtree is more than 1, then the tree is unbalanced
        if (abs(left_height - right_height) > 1):
            return False, height

        return True, height

Мне было интересно, зачем нам 

height = max(left_height, right_height) + 1

Как именно нахождение максимума помогает нам?

Спасибо

...