数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学打印二叉树的所有指数级层
在这个问题中，我们将打印二叉树的所有指数级层。
我们将使用层序遍历来遍历二叉树的每一层。之后，我们将使用该层的第一个元素找到最小P和q值。下一步，我们可以检查其他层的值是否为指数。
问题陈述
我们得到一个二叉树。我们需要打印二叉树所有指数级层的节点值。如果二叉树某一层每个节点的值都等于P^Q，则称为指数级层。这里P是最小常数，Q是P的幂。
示例
输入
2 / \ 3 9
输出
2 3, 9
解释
这里，树的两层都是指数级层。第一层只包含单个值。所以它总是指数级的。第二层的节点值是31和32。所以每个值都以3^Q的形式出现。
输入
2
/ \
16 64
/ \ / \
5 15 20 10
/ \
10 100
输出
25 16 64 10 100
解释
第一、第二和第四层是指数级层。
方法
在这种方法中，我们将获取每一层的节点。之后，我们将第一个节点转换为P^Q的形式。然后，我们将检查是否可以将每个节点转换为P^X的形式。如果是，我们将打印该层。
算法
步骤1 - 调用executeSieve()函数，使用筛法在N+1范围内找到素数。
步骤1.2 - 在executeSieve()函数中，定义大小为N+1的check[]数组，并将其初始化为true，假设所有数字最初都是素数。
步骤1.3 - 使用循环进行2到p*p范围内的迭代。在循环中，如果check[p]为真，则将p插入素数列表。同时，将p的倍数在check[]数组中的值更新为false。
步骤2 - 调用showExpoLevels()函数。在showExpoLevels()函数中，调用getHeight()函数以获取二叉树的高度。在getHeight()函数中，递归遍历树并获取树的最大高度。
步骤3 - 之后，创建一个大小等于树高度的queue[]数组，并将第一个元素初始化为根节点。之后，执行getExpLevels()函数。
步骤3.1 - 在getExpLevels()函数中，创建一个level[]列表来存储每一层的节点。
步骤3.2 - 当索引小于大小限制时进行迭代。同时，使用嵌套循环进行迭代，直到索引小于临时大小，从而遍历特定层。
步骤3.3 - 从队列的'ind'索引中获取第一个节点。将节点值插入levels[]列表中。如果左子节点和右子节点存在，则将它们插入到'queue'列表的末尾。
步骤3.4 - 增加'ind'值。
步骤3.5 - 如果我们已经遍历了特定层，则调用checkForExponential()函数以检查当前层是否是指数级层。
步骤3.5.1 - 在checkForExponential()函数中，调用getXValue()函数来获取x的值。
步骤3.5.2 - 在getXValue()函数中，如果n为1，则返回1。
步骤3.5.3 - 否则，取n的对数，并从2到n进行遍历以找到log(n)的底数。
步骤3.5.4 - 取q的对数。用log(n)/log(q)计算结果。之后，计算(pow(q, int(power)))，如果结果值等于n，则从函数返回x。
步骤3.6 - 获取X值后，使用isVal()函数检查每一层的值是否是X的幂。
步骤3.6.1 - 在isVal()函数中，我们使用对数来检查是否可以将给定值格式化为X的幂。
步骤3.7 - 如果我们无法将层的任何值格式化为X的幂，则返回false。否则，最后返回true。
步骤4 - 如果层是指数级层，则打印该层的所有值。
示例
#include <bits/stdc++.h>
using namespace std;
int N = 1e6;
struct TreeNode {
int val;
struct TreeNode *left, *right;
};
TreeNode *newNode(int val) {
TreeNode *temp = new TreeNode;
temp->val = val;
temp->left = temp->right = NULL;
return (temp);
}
vector<int> prime;
void executeSieve() {
// Initially, all numbers are prime
bool check[N + 1];
memset(check, true, sizeof(check));
for (int p = 2; p * p <= N; p++) {
if (check[p] == true) {
prime.push_back(p);
// Update multiple p
for (int q = p * p; q <= N; q += p)
check[q] = false;
}
}
}
// To check whether number x^n
bool is_val(int n, int x) {
double n_log;
// Get a log
n_log = log10(n) / log10(x);
int num = (int)(pow(x, int(n_log)));
if (n == num)
return true;
return false;
}
int getXValue(int n) {
if (n == 1)
return 1;
double logVal, logq, power;
int x, number;
logVal = log10(n);
for (int q = 2; q <= n; q++) {
logq = log10(q);
power = logVal / logq;
number = (int)(pow(q, int(power)));
if (abs(number - n) < 1e-6) {
x = q;
break;
}
}
return x;
}
bool checkForExponential(vector<int> &level) {
// Get the value of X
int x = getXValue(level[0]);
for (int q = 1; q < level.size(); q++) {
if (!is_val(level[q], x))
return false;
}
return true;
}
void getExpLevels(struct TreeNode *root, struct TreeNode *queue[], int ind, int size) {
vector<int> level;
while (ind < size) {
int tmp_size = size;
while (ind < tmp_size) {
struct TreeNode *temp = queue[ind];
level.push_back(temp->val);
if (temp->left != NULL)
queue[size++] = temp->left;
if (temp->right != NULL)
queue[size++] = temp->right;
// Increment ind
ind++;
}
// check if the level is exponential
if (checkForExponential(level)) {
for (auto ele : level) {
cout << ele << " ";
}
cout << endl;
}
level.clear();
}
}
int getHeight(struct TreeNode *root) {
// Base case
if (root == NULL)
return 0;
return 1 + getHeight(root->left) + getHeight(root->right);
}
void showExpoLevels(struct TreeNode *node) {
int treeSize = getHeight(node);
// Create a queue
struct TreeNode *queue[treeSize];
// Push root node in a queue
queue[0] = node;
getExpLevels(node, queue, 0, 1);
}
int main() {
TreeNode *root = newNode(25);
root->left = newNode(16);
root->right = newNode(64);
root->left->left = newNode(5);
root->left->right = newNode(15);
root->right->left = newNode(20);
root->right->right = newNode(10);
root->right->left->left = newNode(10);
root->right->right->right = newNode(100);
executeSieve();
showExpoLevels(root);
return 0;
}
输出
25 16 64 10 100
时间复杂度 - O(N*N*logN)
空间复杂度 - 计算素数需要O(N*N)。
结论
在这里，我们打印了二叉树的每个指数级层。但是，这个问题对初学者并不友好，但初学者程序员可以尝试编写代码来打印二叉树的所有偶数层或奇数层。如果二叉树的任何一层只包含偶数，则该层称为偶数层，奇数层也类似。
111 次浏览
