JuniorКодЧастоЕщё не отвечали
Подсчёт левых листьев бинарного дерева
Посчитайте левые листья бинарного дерева. Узел — левый лист, если он левый ребёнок своего родителя и сам не имеет детей. Дерево из одного узла (корень) не имеет левых листьев.
Требования:
- Один DFS-обход; свойство «левый» должно быть известно от родителя.
struct Node { Node* left; Node* right; int value; };
int countLeftLeaves(Node* root) {
// ваш код здесь
}Допишите реализацию.
Свойство «левый лист» нельзя решить по одному узлу — оно зависит от родителя. Рекурсируйте, передавая флаг isLeft: узел считается, когда он лист (без детей) и isLeft истинно. Рекурсия в left с isLeft = true, в right с isLeft = false. Корню передаётся isLeft = false. O(n) время.
- ✗Считать все листья независимо от того, левые ли они дети
- ✗Пытаться решить «левость» по самому узлу, а не по контексту родителя
- ✗Считать корень дерева из одного узла левым листом
- →Почему узел не может сам решить, что он левый лист?
- →Как вместо этого просуммировать значения левых листьев?
Оглавление
Задача
Посчитайте левые листья дерева (левый ребёнок без детей). За O(n).
Решение
struct Node { Node* left; Node* right; int value; };
static int dfs(Node* node, bool isLeft) {
if (!node) return 0;
if (!node->left && !node->right) // это лист
return isLeft ? 1 : 0; // считаем только левые
return dfs(node->left, true) // левый ребёнок: isLeft = true
+ dfs(node->right, false); // правый: isLeft = false
}
int countLeftLeaves(Node* root) {
return dfs(root, false); // корень не левый
}Ключевые моменты
- «Левость» приходит от родителя через флаг
isLeft, а не выводится из узла. - Корень передаётся с
isLeft = false, поэтому одиночный корень не считается. - Один DFS-обход, O(n) время.
Оглавление
