資料結構
網路
關係資料庫管理系統 (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 次瀏覽
