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.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
Solution: Recursion
Recursively build a BST for a given range.
def build(nums, l, r):
if l > r: return None
m = l + (r – l) / 2
root = TreeNode(nums[m])
root.left = build(nums, l, m – 1)
root.right = build(nums, m + 1, r)
return root
return build(nums, 0, len(nums) – 1)
Time complexity: O(n)
Space complexity: O(logn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { function<TreeNode*(int l, int r)> build = [&](int l, int r) { if (l > r) return static_cast<TreeNode*>(nullptr); int m = l + (r - l) / 2; TreeNode* root = new TreeNode(nums[m]); root->left = build(l, m - 1); root->right = build(m + 1, r); return root; }; return build(0, nums.size() - 1); } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public TreeNode sortedArrayToBST(int[] nums) { return buildBST(nums, 0, nums.length - 1); } private TreeNode buildBST(int[] nums, int l, int r) { if (l > r) return null; int m = l + (r - l) / 2; TreeNode root = new TreeNode(nums[m]); root.left = buildBST(nums, l, m - 1); root.right = buildBST(nums, m + 1, r); return root; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def buildBST(l: int, r: int) -> TreeNode: if l > r: return None m = l + (r - l) // 2 root = TreeNode(nums[m]) root.left = buildBST(l, m - 1) root.right = buildBST(m + 1, r) return root return buildBST(0, len(nums) - 1) |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua var sortedArrayToBST = function(nums) { var buildBST = function(l, r) { if (l > r) return null; let m = l + Math.floor((r - l) / 2); let root = new TreeNode(nums[m]); root.left = buildBST(l, m - 1); root.right = buildBST(m + 1, r); return root; } return buildBST(0, nums.length - 1); }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment