Java 中二叉树的右视图

在本节中，我们将学习 Java 中的二叉树右视图 以及实现它的不同方法。在二叉树的右视图中，我们只打印当从右侧查看二叉树时可见的二叉树的节点。

对于下面的二叉树

上述二叉树的右视图是

20 8 5 10 7

注意：在二叉树的右视图中，节点显示在输出中的顺序并不重要。重要的是要确保所有从二叉树的右侧可见的节点都包含在输出中。

方法 1：使用递归

方法是使用递归来查找二叉树的右视图。可以向所有递归调用传递一个参数来查找节点的级别。每当我们遇到一个级别大于迄今为止找到的最大级别的节点时，我们就会显示该节点。这是因为它是在此级别遇到的最后一个节点。由于我们需要显示二叉树的右视图，因此我们必须以先访问右子树再访问左子树的方式进行遍历。

实施

让我们看一下使用递归实现二叉树的右视图。以下代码的执行时间为 O(n)，程序使用的堆栈也导致空间复杂度为 O(n)，其中 n 是二叉树中存在的节点总数。

文件名： RightViewExample.java

输出

The following are the nodes present in the right view of the Binary Tree: 
20 8 5 10 7

方法 2：使用 Queue()

如果我们仔细观察，我们会发现二叉树的右视图是每个级别遇到的最后一个节点。因此，我们可以使用队列数据结构来遍历二叉树的每个级别。在每个级别，我们只打印在每个级别找到的最后一个节点的值。

实施

让我们看一下使用队列实现二叉树的右视图。下面程序的 time complexity 为 O(n)，其中 n 是树中存在的节点总数。

文件名： RightViewExample1.java

输出

The following are the nodes present in the right view of the Binary Tree: 
20 8 5 10