|
Convert Sorted Array to Binary Search Tree描述分析代码相关题目Convert Sorted Array to Binary Search Tree描述 Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
分析二分法。
代码// Convert Sorted Array to Binary Search Tree// 二分法，时间复杂度O(n)，空间复杂度O(logn)class Solution {public: TreeNode* sortedArrayToBST (vector& num) { return sortedArrayToBST(num.begin(), num.end()); } template TreeNode* sortedArrayToBST (RandomAccessIterator first, RandomAccessIterator last) { const auto length = distance(first, last); if (length left = sortedArrayToBST(first, mid); root->right = sortedArrayToBST(mid + 1, last); return root; }};
相关题目
Convert Sorted List to Binary Search Tree
原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/binary-tree/bst/convert-sorted-array-to-binary-search-tree.html
|