Есть бинарное дерево, пусть оно будет сбаллансированное. Необходимо найти глубину дерева (максимальное расстояние от корня до листа) и вернуть все пути в дереве (их почти гарантированно несколько) с этой глубиной.
Структура ноды дерева
struct TreeNodeMod {
int data;
struct TreeNodeMod* leftChild;
struct TreeNodeMod* rightChild;
};
Создается бинарное дерево
int * arr = new int[n];
for (size_t i = 0; i < n; i++) {
arr[i] = i;
}
TreeNodeMod * head = CreateBalancedTree(arr, 0, n-1);
Функция создания дерева
TreeNodeMod * CreateBalancedTree(int arr[], int start, int end) {
if (arr == nullptr) {
return nullptr;
}
if (end < start) {
return nullptr;
}
int mid = (start + end) / 2;
TreeNodeMod *n = MakeNode(arr[mid]);
n->leftChild = CreateBalancedTree(arr, start, mid - 1);
n->rightChild = CreateBalancedTree(arr, mid + 1, end);
return n;
}
TreeNodeMod * MakeNode(int x) {
TreeNodeMod * n = new TreeNodeMod;
n->data = x;
n->leftChild = nullptr;
n->rightChild = nullptr;
return n;
}
Сам я дошел только до печати дерева по уровням
void PrintTreeByLevel(TreeNodeMod * n) {
int h = TreeHeight(n);
auto prnt = [](auto&& self, TreeNodeMod * n, int lvl){
if (n == nullptr) {
return;
}
if (lvl == 1) {
std::cout << n->data << " ";
}
else {
if (lvl > 1) {
self(self, n->leftChild, lvl-1);
self(self, n->rightChild, lvl-1);
}
}
};
for (int i = 1; i < h+1; i++) {
prnt(prnt, n, i);
std::cout << std::endl;
}
}
Возможно, для этого можно как-то модифицировать фукцию подсчета глубины дерева, но я не могу сообразить, как
size_t TreeHeight(TreeNodeMod * node) {
if (node == nullptr) {
return 0;
}
else
{
int lheight = TreeHeight(node->leftChild);
int rheight = TreeHeight(node->rightChild);
if (lheight > rheight)
return(lheight + 1);
else
return(rheight + 1);
}
}
Буду рад любым подсказкам и советам.