Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/108.html
108 Convert Sorted Array to Binary
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
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
@tag-tree
Algorithm
The root node should be the middle point of the ordered array, separated from the middle point into two left and right ordered arrays, and find out the left and right child nodes whose middle point is the original middle point.
Code
Java
-
import java.util.Arrays; public class Convert_Sorted_Array_to_Binary_Search_Tree { public static void main(String[] args) { Convert_Sorted_Array_to_Binary_Search_Tree out = new Convert_Sorted_Array_to_Binary_Search_Tree(); Solution s = out.new Solution(); int[] a = {1, 2, 3, 4, 5}; int[] b = Arrays.copyOfRange(a, 0, a.length); System.out.println(Arrays.toString(b)); // b = Arrays.copyOfRange(a, 2, 1); // error, must to > from b = Arrays.copyOfRange(a, 2, 2); // ok, empty array returned System.out.println("a, 2, 2: " + Arrays.toString(b)); // b = Arrays.copyOfRange(a, -1, 10); // error, out of boundary // System.out.println("a, -1, 10" + Arrays.toString(b)); b = Arrays.copyOfRange(a, a.length, a.length); // ok, empty array returned System.out.println("a, a.length, a.length: " + Arrays.toString(b)); } /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums == null || nums.length == 0) return null; return dfs(nums, 0, nums.length - 1); } TreeNode dfs(int[] nums, int left, int right) { if (left > right) return null; int mid = left + (right - left) / 2; TreeNode cur = new TreeNode(nums[mid]); cur.left = dfs(nums, left, mid - 1); cur.right = dfs(nums, mid + 1, right); return cur; } } }
-
// OJ: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/ // Time: O(N) // Space: O(logN) class Solution { TreeNode *dfs(vector<int> &A, int begin, int end) { if (begin + 1 > end) return NULL; int mid = (begin + end) / 2; auto root = new TreeNode(A[mid]); root->left = dfs(A, begin, mid); root->right = dfs(A, mid + 1, end); return root; } public: TreeNode* sortedArrayToBST(vector<int>& A) { return dfs(A, 0, A.size()); } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: def dfs(l, r): if l > r: return None mid = (l + r) >> 1 left = dfs(l, mid - 1) right = dfs(mid + 1, r) return TreeNode(nums[mid], left, right) return dfs(0, len(nums) - 1) ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: def dfs(l, r): if l > r: return None mid = (l + r) >> 1 left = dfs(l, mid - 1) right = dfs(mid + 1, r) return TreeNode(nums[mid], left, right) return dfs(0, len(nums) - 1) ############ # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ if nums: midPos = len(nums) / 2 mid = nums[midPos] root = TreeNode(mid) root.left = self.sortedArrayToBST(nums[:midPos]) root.right = self.sortedArrayToBST(nums[midPos + 1:]) return root