Java 中的逆层序遍历

我们已经在这里讨论过 层序遍历。在本教程中，我们将讨论如何在 Java 中执行反向层序遍历。在输入中，会给出一个二叉树，我们的任务是以反向层序模式打印包含在各种子节点中的值。

示例 1

输入

输出 15, 35, 50, 12, 16, 90, 17, 19, 11

示例 2

输入

输出：16, 17, 14, 15, 12, 13, 11

方法：使用递归

在层序遍历中，每一层的值都从左到右打印。现在，在本例中，我们需要递归遍历所有层，然后从右到左打印。但是，在此之前，我们必须知道二叉树中有多少层。要找到这一点，我们只需要找到树的高度。其实现如下。

文件名：ReverseLevelOrderRec.java

输出

The reverse Level Order traversal of the binary tree is: 
15 35 50 12 16 90 17 19 11 

The reverse Level Order traversal of the binary tree is: 
16 17 14 15 12 13 11

复杂度分析：程序的复杂度分析为 O(n²)，程序的空间复杂度为 O(h)，其中 h 是二叉树的高度。

方法：使用队列和栈

在这种方法中，我们将使用队列和栈。首先，我们将根节点放入队列，然后是它的右子节点和左子节点（如果存在）。之后，弹出父节点并将其推入栈。现在从队列中弹出右子节点，它现在是父节点，并将其推入栈。将父节点的右子节点和左子节点放入队列。重复上述过程处理其他节点，直到队列为空。现在，使用循环，弹出插入栈中的节点并打印它们的值。这样，我们就可以在不使用递归的情况下执行反向层序遍历。

文件名：BinaryTreeItr.java

输出

The reverse Level Order traversal of the binary tree is: 
15 35 50 12 16 90 17 19 11 

The reverse Level Order traversal of the binary tree is: 
16 17 14 15 12 13 11

复杂度分析：程序的复杂度分析为 O(n²)，程序的空间复杂度为 O(h)，其中 h 是二叉树的高度。