二叉搜索树按以下顺序递归遍历 右根 左

Question

通常我们按顺序、前序或后序遍历二叉搜索树。但是，当我们按照以下递归顺序从右 - 根 - 左遍历二叉搜索树时会发生什么？

假设我是否将值存储在数组中，并且与预序遍历相比，当我们按此顺序进行遍历时，它的时间复杂度是否增加。

Answer 1

让我们使用一个示例二叉搜索树：

                  5
                /   
               3     7
              /    /  
             2   4 6    8

按顺序遍历（左树、根、右树）

2 3 4 5 6 7 8

我们是怎么做到的？

伪代码：

InorderTraversal(root)
{
   if root is not null:
      InorderTraversal(root.left)
      print root
      InorderTraversal(root.right)
}

让我们在我们的树上玩电脑

• 从根开始 （5）
• 根 （5） 不为空，因此请访问左侧
• 根 （3） 不为空，因此请向左访问
• 根 （2） 不为空，因此请访问左侧
• 根 （空） 为空，返回
• 打印 2
• 访问右边的2棵树
• 根 （空） 为空，返回
• 打印根 （3）
• 访问右边的3棵树
• 根 （4） 不为空，访问左侧
• 根 （空） 为空，返回
• 打印根 （4）
• 访问右边的4棵树
• 根 （空） 为空，返回
• 打印根 （5）
• 访问右边的5棵树
• 根 （7） 不为空
• 。
• 打印根 （8）
• 访问根的右子树 （8）
• 根 （空） 为空，返回

右根左遍历

8 7 6 5 4 3 2

伪代码：

RightRootLeftTraversal(root)
{
   if root is not null:
      RightRootLeftTraversal(root.right)
      print root
      RightRootLeftTraversal(root.left)
}

如您所见，这与顺序遍历的顺序完全相反。在二叉搜索树上，我们将得到反向顺序遍历。

操作数与预序遍历相同，即 O（n），因为我们访问每个节点一次。