打印二叉树的所有回文层

---

在这个问题中，我们将打印给定二叉树中所有回文层。我们可以使用广度优先搜索算法遍历给定二叉树的每一层，并检查二叉树的特定层是否为回文。如果是，则在输出中打印该层。

问题陈述 - 我们给定一个二叉树，我们需要打印二叉树的所有回文层。如果二叉树的任何特定层从左到右和从右到左包含相同的数字，我们可以说当前层是回文。

示例

输入

                  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)，因为我们将二叉树的节点存储在队列中。

我们学习了如何遍历二叉树的每一层并检查是否有任何层是回文。此外，程序员可以尝试编写代码来打印他们需要打印偶数层的代码。我们需要打印仅包含偶数的层。