🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1469. Find All The Lonely Nodes
Сложность: easy
В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.
Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке.
Пример:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.
👨💻 Алгоритм:
1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.
2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.
3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.
😎 Решение:
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
void DFS(TreeNode* root, bool isLonely, vector& ans) {
if (root == NULL) {
return;
}
if (isLonely) {
ans.push_back(root->val);
}
DFS(root->left, root->right == NULL, ans);
DFS(root->right, root->left == NULL, ans);
}
vector getLonelyNodes(TreeNode* root) {
vector ans;
DFS(root, false, ans);
return ans;
}
};
Ставь 👍 и забирай 📚 Базу знаний
