Блог

Я работаю над проблемой кода 104. Максимальная глубина двоичного дерева:

Учитывая root размер двоичного дерева, верните его максимальную глубину.

Максимальная глубина двоичного дерева-это количество узлов вдоль самого длинного пути от корневого узла до самого дальнего конечного узла.

Моя попытка не работает: я сначала добавляю root его в очередь (если root это не None так ), а затем обрабатываю его, добавляя его дочерние элементы в очередь.

При этом я сохраняю счетчик, и каждый раз, когда я добавляю дочерний узел, я увеличиваю счетчик на 1. Когда существуют как левый, так и правый дочерний элемент, я увеличу счетчик только на 1.

 from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def max_depth(self,root):
        counter = 1
        queue = deque
        
        if not root: 
            return 0
        else:
            queue.append(root)

        while queue:
            root = queue.popleft()

            if root.left:
                queue.append(root.left)
                counter  =1

            if root.right:
                queue.append(root.right)
                if root.left:
                    continue
                else:
                    counter  =1

        return counter
 

Однако, когда я запускаю вышеописанное в коде LEET для ввода, скажем, [3,9,20,null,null,15, 7], в результате я получаю «Нет».

Это потому, что я структурировал функцию так, чтобы не принимать список в качестве входных данных?

Это потому, что я структурировал функцию так, чтобы не принимать список в качестве входных данных?

Нет. Это может сбивать с толку, но в LeetCode представление исходного списка входных данных преобразуется в экземпляр TreeNode перед вызовом вашей функции. Поэтому вам никогда не придется иметь дело с этой структурой списков. Это просто общий формат ввода, который LeetCode использует в разных языках программирования. Но преобразование в структуру данных целевого языка выполняется за вас до вызова вашей реализации.

Ваш код выдает ошибку при первом вызове из queue.append -за этой строки:

 queue = deque
 

Это неправильно, так как это делает queue синоним класса deque . Но это должен быть пример этого, так что делайте:

 queue = deque()
 

С этим исправлением функция не возвращается None .

Однако его логика неверна:

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

Это практически означает, что вы подсчитываете количество узлов, у которых есть хотя бы один дочерний элемент, т. е. вы подсчитываете количество внутренних узлов дерева. Это неверно. Например, следующее дерево имеет 7 внутренних узлов:

                  ___ 10 __
                /         
               5           14
             /           /   
            1     8     12     20
           /    /    /     /  
          0   2 6   9 11  13 18  22
 

Очевидно, что 7 — это неправильный ответ. В данном случае должно быть 4.

Ваше решение на основе очереди будет посещать узлы уровень за уровнем, но у вас нет никакой информации о том, когда вы переходите с одного уровня на другой.

Вы можете решить эту проблему с помощью двух (стандартных) списков: в первом списке будут все узлы с одного уровня, а во втором списке будут собраны узлы со следующего уровня. Когда это будет сделано, вы будете знать, что прошли один уровень. Затем вы делаете второй список первым, а второй опустошаете. Затем вы можете перезапустить этот процесс до тех пор, пока будут обрабатываться узлы:

 class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        counter = 0
        queue = []
        
        if root: 
            queue.append(root)

        while queue:
            counter  =1
            nextlevel = []
            
            for root in queue:
                if root.left:
                    nextlevel.append(root.left)
                if root.right:
                    nextlevel.append(root.right)
            queue = nextlevel

        return counter
 

Сделав его немного более компактным, он может быть:

 class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        counter = 0
        if root: 
            queue = [root]
            while queue:
                counter  =1
                queue = [root.left for root in queue if root.left
                        ]   [root.right for root in queue if root.right]
        return counter
 

Вы также можете выполнить обход сначала по глубине, а не по ширине, как вы собирались:

 class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        return 1   max(self.maxDepth(root.left), 
                       self.maxDepth(root.right)) if root else 0