public class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue q = new LinkedList<>();
TreeNode rightMost = root;
q.add(root);
int depth = 1;
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node.left == null && node.right == null) {
break;
}
if (node.left != null) {
q.add(node.left);
}
if (node.right != null) {
q.add(node.right);
}
if (node == rightMost) {
depth++;
rightMost = (node.right != null) ? node.right : node.left;
}
}
return depth;
}
}
Мы используем BFS для решения этой проблемы. Мы добавляем узлы на том же уровне в очередь q . Мы перебираем каждый из узлов. Когда мы сталкиваемся с конечным узлом, мы останавливаемся и возвращаем depth (минимальная глубина). После перебора всех узлов на том же уровне мы все еще не можем найти конечный узел, мы увеличиваем глубину на 1, затем повторяем описанный выше процесс для узлов на следующем уровне. Мы также можем использовать DFS. Однако BFS превосходит DFS на сильно несбалансированных деревьях, поскольку она завершается, как только достигает первого конечного узла.
Временная сложность : O(n)
Дополнительное пространство : O(1)
Оригинал: “https://dev.to/algobot76/leetcode-111-minimum-depth-of-binary-tree-302j”