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

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）
• Root（5）不为空，因此请访问left
• 根（3）不为空，因此请访问左侧
• 根（2）不为空，因此请访问左侧
• Root（null）为null，返回
• 打印2
• 访问右树2
• Root（null）为null，返回
• 打印根目录（3）
• 访问右三棵树
• Root（4）不为空，请访问左侧
• Root（null）为null，返回
• 打印根目录（4）
• 访问右四棵树
• root（null）为null，返回
• 打印根目录（5）
• 访问右五棵树
• 根（7）不为空
• 打印根目录（8）
• 访问根的右子树（8）
• root（null）为null，返回

右根左遍历

8 7 6 5 4 3 2

伪代码：

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

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

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