# 问题 原题链接：[https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/) Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example: ``` Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0 / \ -3 9 / / -10 5 ``` # 分析过程 - 输入：已经排序的数组 - 输出：根据数组生成的二叉搜索树 - 思路：取数组中点作为根，左右递归即可。需要注意的是结果是不唯一的，题中的 case 对应两种树结构，具体见注释。 # 解决方法 ```cpp class Solution { public: TreeNode *_sortedArrayToBST(vector<int>& arr, int left, int right) { if (left > right) { return nullptr; } // 以下树对应的是以下m的取法 // 0 // / \ // -3 5 // / \ // -10 9 // // int m = left + (right - left) / 2; // 以下树对应的是以下m的取法 // 0 // / \ // -3 9 // / / // -10 5 // // 本质的区别是，偶数长度时，取中间靠前那个为根，还是靠后那个为根 // 题目要求的是这一种 int m = left + (right - left) / 2; TreeNode *root = new TreeNode(arr[m]); root->left = _sortedArrayToBST(arr, left, m - 1); root->right = _sortedArrayToBST(arr, m + 1, right); return root; } TreeNode* sortedArrayToBST(vector<int>& nums) { return _sortedArrayToBST(nums, 0, (int)nums.size() - 1); } }; ```