题解 | #将升序数组转化为平衡二叉搜索树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
  public:
    /**
     * 
     * @param num int整型vector 
     * @return TreeNode类
     */
    TreeNode* sortedArrayToBST(vector<int>& num) {
      //  平衡二叉树的中序遍历就是递增数组
      if (num.empty()) {
        return nullptr;
      }
      
      return curision(num, 0, num.size() - 1);
    }
  private:
  //  递归、分治最后归并
    TreeNode* curision(std::vector<int> &num, int left, int right) {
      if (left > right) {
        return nullptr;
      }
      
      int mid = left + (right - left) / 2;
      
      TreeNode *l = curision(num, left,  mid - 1);
      TreeNode *r = curision(num, mid + 1, right);
      
      TreeNode *root = new TreeNode(num[mid]);
      root->left = l;
      root->right = r;
      
      return root;
    }
};