Java 中打印二叉树的所有回文级别

给定一个二叉树，任务是打印该树中的每个回文层。回文层二叉树的任何层如果从左到右遍历和从右到左遍历的结果相同，则被认为是回文层。

示例 1

输入

输出

二叉树的回文层

 
5
3 8 8 3
4 4   

解释

由于第 1、3 和 4 层从前向后和从后向前都相同，因此它们是回文层。

示例 2

输入

输出

二叉树的回文层

 
10
30 40 40 30   

解释

由于第 1 层和第 3 层从前向后和从后向前都相同，因此它们是回文层。

示例 3

输入

输出

二叉树的回文层

 
15
25 25
35 45 45 35
55 65 65 55   

解释

由于第 1、2、3 和 4 层从前向后和从后向前都相同，因此它们是回文层。

方法：使用广度优先搜索

给定的Java程序使用广度优先搜索 (BFS)技术，通过逐层遍历二叉树来查找回文层。为了在层序遍历中处理节点，它使用了基于队列的方法（LinkedList），确保在深入树的下一层之前，访问完指定深度的所有节点。由于在遍历过程中，每一层的节点值都存储在ArrayList中，因此可以使用双指针技术快速比较值序列是否为回文。为了确保对树进行彻底的逐层扫描，程序会系统地出队节点，查找左右子节点（l 和 r），并将它们入队以便在后续轮次中处理。为了获得最佳性能，isPalindrome() 函数使用恒定空间的双指针方法来对称地比较列表两端的元素。

算法

步骤 1：创建一个节点结构，每个节点包含一个键 (k) 以及指向左子节点 (l) 和右子节点 (r) 的指针。

步骤 2：存储当前层节点值的列表。

步骤 3：通过使用双指针技术，可以从两端比较元素。

步骤 4：如果该层是回文层，则返回 true；否则返回 false。

步骤 5：使用 LinkedList 作为队列进行 BFS 遍历。

步骤 6：在逐层处理节点时存储节点的值。

步骤 7：将左右子节点（l 和 r）添加到队列中，以便进入下一层。

步骤 8：验证每一层是否为回文层。

步骤 9：如果该层是回文层，则打印该层。

实施

输出

 
The Palindromic Levels of a Binary Tree
15 
25 25 
35 45 45 35 
55 65 65 55   

复杂度分析

上述代码的时间复杂度为 O(N^2)，空间复杂度为 O(N)，其中“N”表示节点的数量。