Convert Sorted Array to Binary Search Tree

描述

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

分析

二分法。

代码

  1. // Convert Sorted Array to Binary Search Tree
  2. // 二分法，时间复杂度O(n)，空间复杂度O(logn)
  3. class Solution {
  4. public:
  5.     TreeNode* sortedArrayToBST (vector& num) {
  6.         return sortedArrayToBST(num.begin(), num.end());
  7.     }
  9.     template
  10.     TreeNode* sortedArrayToBST (RandomAccessIterator first,
  11.             RandomAccessIterator last) {
  12.         const auto length = distance(first, last);
  14.         if (length left = sortedArrayToBST(first, mid);
  15.         root->right = sortedArrayToBST(mid + 1, last);
  17.         return root;
  18.     }
  19. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/binary-tree/bst/convert-sorted-array-to-binary-search-tree.html