Leetcode 108. Convert Sorted Array to Binary Search Tree
程序员文章站
2022-07-15 12:42:45
...
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.
method 1
本题只要熟悉概念就会做,构造的二叉树要求是AVL树,那么我们可以使用分治法,取中间的数作为根节点,然后对左右两边采取同样的操作
TreeNode* helper(vector<int>& nums, int low, int high){
if (low > high) return NULL;
int mid = (low + high) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = helper(nums, low, mid - 1);
root->right = helper(nums, mid + 1, high);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0)
return NULL;
return helper(nums, 0, nums.size() - 1);
}
summary
- 大问题可以化为小问题–> 分治法
推荐阅读
-
Convert Sorted Array to Binary Search Tree
-
Leetcode——108. Convert Sorted Array to Binary Search Tree
-
Leetcode 108. Convert Sorted Array to Binary Search Tree
-
Leetcode No.108 Convert Sorted Array to Binary Search Tree(c++实现)
-
convert-sorted-array-to-binary-search-tree 将有序数组转换为二叉搜索树
-
Convert Sorted Array to Binary Search Tree
-
108. Convert Sorted Array to Binary Search Tree
-
109. Convert Sorted List to Binary Search Tree
-
108. Convert Sorted Array to Binary Search Tree
-
【LeetCode】convert-sorted-list-to-binary-search-tree