看到题目我的第一个问题是“什么是二叉搜索树？” ，唉，大学没有好好学算法，现在开始一点一点补吧。

二叉搜索树

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构

所以就是如下的答案（答案不止一个）。

那么这种树形结构为什么叫二叉搜索树（二叉排序树）呢？因为这种树形结构在查找元素上比较快。

🌰：

如果我们想要找元素 6 需要几步呢？

1. 先和根元素 4 比较，大于根元素 4 ，根据二叉搜索树的特性 —— 右子树上所有结点的值均大于它的根结点的值；所以目标元素在右子树上；
2. 比较 6 和 7 ,发现 6 小于 7 ，根据二叉搜索树的特性 —— 左子树上所有结点的值均小于它的根结点的值；所以目标元素在以 7 为根节点子树的左子树上。
3. 比较 6 和 5 , 发现 6 大于 5 ，所以在以 5 为根节点的子树的右边孩子节点中寻找。
4. 找到元素 6

只进行了 4 次查找，并且查找的最大次数也就是数的深度。（有一点像二分查找）

平衡二叉搜索树

题目中要的是 平衡二叉搜索树，多了 平衡 两个字，其实也就是在二叉搜索树的基础上对其左右子树的深度进行了限制。

所以平衡二叉搜索树的特点是：

1. 为空树
2. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
3. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
4. 它的左、右子树也分别为二叉排序树。
5. 每个左右子树的高度差的绝对值不能大于1；

那么我们就根据 平衡二叉搜索树 的特性就比较好写了。

1. 先找到根节点（因为平衡树左右子树，所以选取数组的中间那个元素为根元素，这样才能 平衡）；
2. 对左边子节点递归调用生成树的 dfs，返回一个树；

3. 对右边子节点递归调用生成树的 dfs，返回一个树；

   /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   * };
   */
   class Solution {
   public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int length = nums.size();
        return dfs(nums, 0, length - 1 );
    }
    TreeNode* dfs(vector<int> subNums,int left,int right){
        if(left > right){
            return nullptr;
        }
        int length = subNums.size();
        int middlendex = (left + right) / 2;
        TreeNode* root = new TreeNode(subNums[middlendex]);
        root->left = dfs(subNums, left, middlendex - 1);
        root->right = dfs(subNums, middlendex + 1, right);
        return root;
    }
   };