题目

108 将升序数组转换为二叉树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
image.png

思路

其实这里不用强调平衡二叉搜索树，数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取。
本题本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。本体输出结果不唯一，如果要分割的数组长度为偶数的时候，中间元素为两个，是取左边元素就是树1，取右边元素就是树2。
image.png

  1. class Solution
  2. {
  3. public:
  4.     TreeNode *sortedArrayToBST(vector<int> &nums)
  5.     {
  6.         return buildAVL(nums, 0, nums.size() - 1);
  7.     }
  9. private:
  10.     TreeNode *buildAVL(vector<int> &nums, int left, int right)
  11.     {
  12.         if (left > right)
  13.             return nullptr;
  14.         else if (left == right)
  15.             return new TreeNode(nums[left]);
  17.         int mid = (left + right) / 2; //默认取左边元素，生成树1
  18.         //int mid = ((left + right) % 2 == 0) ? (left + right) / 2: (left + right) / 2+1; //生成树2
  19.         TreeNode *node = new TreeNode(nums[mid]);
  20.         node->left = buildAVL(nums, left, mid - 1);
  21.         node->right = buildAVL(nums, mid + 1, right);
  22.         return node;
  23.     }
  24. };