Блог

Я знаю, что это может быть тривиально, но я просто хочу убедиться. Я считаю, что время выполнения будет не более O (n). Я рассуждаю о том, что каждый узел будет возвращать значение высоты один раз в течение этого рекурсивного метода. Или, другими словами, мы посетим каждый узел в дереве один раз.

     def height(self):
        if self.is_empty():
            return 0
        else:
            left_max = self._left.height()
            right_max = self._right.height()
            return max(left_max, right_max)   1
 

• Вы выполняете обход DFS по дереву, все узлы будут посещены только один раз.
• Так что, очевидно, это займет только время O (N).