111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

111. Минимальная глубина бинарного дерева

Задано бинарное дерево. Найдите его наименьшую глубину.

Наименьшей глубиной дерева называется количество вершин на пути от корня до ближайшего листа.

class Solution {

public:

int minDepth(TreeNode* root) {

}

};

РЕШЕНИЕ

структуры данных - деревья

Анализ алгоритма

Если root = NULL, то глубина дерева равна 0.

Если корень дерева не имеет левого поддерева, то ищем глубину правого.

Если корень дерева не имеет правого поддерева, то ищем глубину левого.

Если корень дерева имеет оба сына, то ищем глубину левого Left и правого Right поддерева. Минимальная глубина самого дерева равна

min(Left, Right) + 1

Реализация алгоритма

class Solution

{

public:

int minDepth(TreeNode* root)

{

if (root == NULL)

return 0;

if (root->left == NULL)

return minDepth(root->right) + 1;

if (root->right == NULL)

return minDepth(root->left) + 1;

int Left = minDepth(root->left);

int Right = minDepth(root->right);

return min(Left,Right) + 1;

}

};