列印二叉樹的所有迴文層

---

在這個問題中，我們將列印給定二叉樹中所有迴文層。我們可以使用廣度優先搜尋演算法遍歷給定二叉樹的每一層，並檢查二叉樹的特定層是否為迴文。如果是，則在輸出中列印該層。

問題陳述 - 我們給定一個二叉樹，我們需要列印二叉樹的所有迴文層。如果二叉樹的任何特定層從左到右和從右到左包含相同的數字，我們可以說當前層是迴文。

示例

輸入

                  9      
                /    \ 
              23      83 
            /        /   \ 
           90      76     90 
                   \    / 
                   7   7  

輸出

9
90  76  90
7  7

解釋 - 第一、三和四層是迴文。

輸入

                  19
                /    \ 
              23    23 
            /        /   \ 
          80      80     80 
                   \    / 
                   4   4  

輸出

19
23  23
80  80  80
4  4

解釋 - 二叉樹的所有層都是迴文。

方法 1

在本方法中，我們將使用佇列資料結構對二叉樹執行層序遍歷。層序遍歷遍歷二叉樹的每一層。在遍歷每一層時，我們可以檢查當前層是否是迴文。

演算法

步驟 1 - 建立二叉樹節點的結構。

步驟 2 - 定義 createNewNode() 函式來建立一個新的二叉樹節點。createNewNode() 函式建立一個新節點並將左右指標初始化為 NULL。

步驟 3 - 在 main() 方法中建立一個二叉樹。

步驟 4 - 執行 getSize() 函式以獲取二叉樹的高度。

步驟 4.1 - 在 getSize() 函式中，如果頭節點為 NULL，則返回 0。

步驟 4.2 - 否則，對當前節點的左子節點和右子節點進行遞迴呼叫，並將 1 加到其返回值。

步驟 5 - 建立一個大小等於二叉樹高度的佇列，並將頭節點插入佇列。

步驟 6 - 執行 printPalindromicLevel() 函式以遍歷每一層並查找回文層。

步驟 6.1 - 列印第一個節點，因為它總是迴文。

步驟 6.2 - 使用 while 迴圈進行迭代，直到 'ind' 小於 'size' 以遍歷每一層。

步驟 6.3 - 使用另一個 while 迴圈遍歷當前層。

步驟 6.4 - 在巢狀的 while 迴圈中，從佇列中取出當前節點。

步驟 6.5 - 如果當前節點的左子節點和右子節點存在，則將其插入佇列。

步驟 6.6 - 將 'ind' 加 1。

步驟 6.7 - 執行 isLevelPalindrome() 函式以檢查當前層是否是迴文。

步驟 6.7.1 - 遍歷佇列，並比較從開始到結束的元素。

步驟 6.7.2 - 如果任何元素與開頭和結尾不匹配，則返回 false。

步驟 6.7.3 - 最後返回 true。

步驟 6.8 - 如果 isLevelPalindrome() 為真，則執行 showLevel() 函式以列印當前層。在函式中，我們遍歷佇列並列印佇列的每個元素。

示例

#include <bits/stdc++.h>
using namespace std;
// Tree structure
struct TreeNode {
    int val;
    struct TreeNode *left, *right;
};
// Function for creating new node
TreeNode *createNewNode(int val) {
    TreeNode *tmp = new TreeNode;
    tmp->val = val;
    tmp->left = NULL;
    tmp->right = NULL;
    return (tmp);
}
bool isLevelPalindrome(struct TreeNode *que[], int ind, int sz) {
    while (ind < sz) {
        // Check for the palindrome string
        if (que[ind++]->val != que[sz--]->val)
            return false;
    }
    return true;
}
// Print the particular level of a given
void showLevel(struct TreeNode *que[], int ind, int sz) {
    // Traverse the queue and print all values
    for (int p = ind; p < sz; p++) {
        cout << que[p]->val << " ";
    }
    cout << endl;
}
void printPalindromicLevel(struct TreeNode *head, struct TreeNode *que[], int ind, int size) {
    // Root node is always palindrome
    cout << que[ind]->val << endl;
    while (ind < size) {
        int temp_size = size;
        while (ind < temp_size) { 
            struct TreeNode *temp = que[ind];
            if (temp->left != NULL) {
                que[size++] = temp->left;
            }
            if (temp->right != NULL) {
                que[size++] = temp->right;
            }
            ind++;
        }
        if (isLevelPalindrome(que, ind, size - 1)) {
            showLevel(que, ind, size);
        }
    }
}
// Get the size of the tree
int getSize(struct TreeNode *head) {
    // Base condition
    if (head == NULL)
        return 0;
    return 1 + getSize(head->left) + getSize(head->right);
}
void showPalindromeLevel(struct TreeNode *head) {
    int temp_size = getSize(head);
    struct TreeNode *que[temp_size];
    que[0] = head;
    printPalindromicLevel(head, que, 0, 1);
}
int main() {
    TreeNode *head = createNewNode(5);
    head->left = createNewNode(11);
    head->right = createNewNode(11);
    head->left->left = createNewNode(3);
    head->left->right = createNewNode(5);
    head->right->right = createNewNode(3);
    head->left->left->left = createNewNode(54);
    head->left->left->right = createNewNode(17);
    cout << "The palindromic levels are - "<< endl;
    showPalindromeLevel(head);
    return 0;
}

輸出

The palindromic levels are − 
5
11 11 
3 5 3 

時間複雜度 - O(N)，因為我們遍歷每個節點。

空間複雜度 - O(N)，因為我們將二叉樹的節點儲存在佇列中。

我們學習瞭如何遍歷二叉樹的每一層並檢查是否有任何層是迴文。此外，程式設計師可以嘗試編寫程式碼來列印他們需要列印偶數層的程式碼。我們需要列印僅包含偶數的層。