Поиск минимальной высоты двоичного дерева

Question

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

int minDepth(TreeNode root) { 
    if (root == null) { return 0;} 
     return 1 + Math.min(minDepth(root.left), minDepth(root.right)); 
} 

Однако, я думаю, что он не различает между листом и узлом только с одним ребенком, и поэтому она возвращает Неверное значение. Например, если наше дерево выглядит следующим образом:

А Root

Б левого ребенок A

С является правильным ребенок B

М является левым потомком C

Эта функция возвращает одно в то время как лист 3 хмель от корня и поэтому высота мин 4.

так как это рекурсивная версия, как правило, су В литературе я думаю, что чего-то не хватает.

Может ли кто-нибудь очистить это для меня?

Answer 1

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

Просто возьмите третье простейшее двоичное дерево, состоящее из двух узлов. Он имеет ровно один лист, его глубина - две, а минимальная глубина - также две. Но алгоритм, который вы указали, возвращает значение one. Таким образом, если авторы не используют другое определение для одного из терминов (например, «минимальная высота», означающая «кратчайший путь из дерева»/«кратчайший путь к нулевому указателю»), результат просто неверен.