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

• Java
• C++
• Python

• 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
  
  

All Problems

All Solutions