如何将有序数组转换为二叉搜索树

一、什么是二叉搜索树

二叉搜索树（Binary Search Tree），又称为二叉查找树、有序二叉树，是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

3. 任意节点的左、右子树也分别为二叉查找树；

4. 没有键值相等的节点。

二、将有序数组转换为二叉搜索树

将有序数组转换为二叉搜索树的过程，主要是将数组的中间元素作为根节点，将数组分成左右两个部分，然后递归的将左右两个部分转换成二叉搜索树。具体步骤如下：

1、计算数组的中间元素

首先，我们需要计算数组的中间元素，将中间元素作为根节点，比如给定数组[1,2,3,4,5,6,7]，中间元素为4，即根节点为4。

2、将数组分成两部分

然后，我们将数组分成两部分，左边部分为[1,2,3]，右边部分为[5,6,7]。

3、递归将左右两部分转换为二叉搜索树

接着，我们递归的将左右两部分转换为二叉搜索树，即将左边部分转换为一棵二叉搜索树，将右边部分转换为一棵二叉搜索树，根节点分别为2和6，如下图所示：


4、拼接根节点和左右子树

最后，我们拼接根节点和左右子树，即将根节点4和左右子树[2]和[6]拼接起来，得到一棵二叉搜索树，如下图所示：