Question

Formatted question description: https://leetcode.ca/all/108.html

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

1 <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴
nums is sorted in a strictly increasing order.

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

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;
        }
    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int[] nums;

    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return dfs(0, nums.length - 1);
    }

    private TreeNode dfs(int l, int r) {
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        TreeNode left = dfs(l, mid - 1);
        TreeNode right = dfs(mid + 1, r);
        return new TreeNode(nums[mid], left, right);
    }
}

// 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(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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
	var dfs func(int, int) *TreeNode
	dfs = func(l, r int) *TreeNode {
		if l > r {
			return nil
		}
		mid := (l + r) >> 1
		left, right := dfs(l, mid-1), dfs(mid+1, r)
		return &TreeNode{nums[mid], left, right}
	}
	return dfs(0, len(nums)-1)
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sortedArrayToBST(nums: number[]): TreeNode | null {
    const n = nums.length;
    if (n === 0) {
        return null;
    }
    const mid = n >> 1;
    return new TreeNode(
        nums[mid],
        sortedArrayToBST(nums.slice(0, mid)),
        sortedArrayToBST(nums.slice(mid + 1)),
    );
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
    const dfs = (l, r) => {
        if (l > r) {
            return null;
        }
        const mid = (l + r) >> 1;
        const left = dfs(l, mid - 1);
        const right = dfs(mid + 1, r);
        return new TreeNode(nums[mid], left, right);
    };
    return dfs(0, nums.length - 1);
};

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn to_bst(nums: &Vec<i32>, start: usize, end: usize) -> Option<Rc<RefCell<TreeNode>>> {
        if start >= end {
            return None;
        }
        let mid = start + (end - start) / 2;
        Some(Rc::new(RefCell::new(TreeNode {
            val: nums[mid],
            left: Self::to_bst(nums, start, mid),
            right: Self::to_bst(nums, mid + 1, end),
        })))
    }

    pub fn sorted_array_to_bst(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Self::to_bst(&nums, 0, nums.len())
    }
}

108 - Convert Sorted Array to Binary Search Tree

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions