LeetCode 之 108. 将有序数组转换为二叉搜索树

思路：

二叉搜索树的定义：它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；

基于题目给的是排序的数组，取中间点作为root，递归构造左右子数即可；

python/python3：

1 class Solution:

2     def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

3         if not nums:

4             return None

5         root_index = int(len(nums)/2)

6         root = TreeNode(nums[root_index])

7         root.left = self.sortedArrayToBST(nums[:root_index])

8         root.right = self.sortedArrayToBST(nums[root_index+1:])

9         return root

C++:

 1 class Solution {

 2 public:

 3     TreeNode* sortedArrayToBST(vector<int>& nums) {

 4         if(nums.size() == 0){

 5             return NULL;

 6         }

 7         int root_index = nums.size()/2;

 8         TreeNode* root = new TreeNode(nums[root_index]);

 9         vector<int> left_nums(nums.begin(), nums.begin()+root_index);

10         vector<int> right_nums(nums.begin()+root_index+1, nums.end());

11         root->left = sortedArrayToBST(left_nums);

12         root->right = sortedArrayToBST(right_nums);

13         return root;

14     }

15 };

巴特西

LeetCode 之 108. 将有序数组转换为二叉搜索树

最新文章

热门文章