LeetCode每日一题：将有序数组转化为二叉搜索树
传送门 二叉搜索树是一颗特殊的二叉树，它满足以下条件： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左右子树也都是二叉搜索树 显然这是一个递归定义，而且不难想到，对于同样一组数据，它们转化得到的二叉搜索树是不唯一的。树的长相取决于根节点的值以及左右子树的取值。 但是一颗太过于畸形的二叉搜索树会给查找带来很高的时间复杂度，所以我们定义了平衡二叉搜索树。它的定义与二叉搜索树稍有不同： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左子树与右子树的高度差的绝对值小于等于1左右子树也都是平衡二叉搜索树 同时定义平衡因子为节点左子树与右子树深度之差。 那么看回这道题。题目要求构建一颗高度平衡的二叉搜索树，那么不难想到做法：取序列的中间值为根，其左右两边的数据为左右子，递归执行上述操作。这种做法的正确性是显然地，详见这里。那么代码就不难写了。 ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), …