PattySung

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.

<解題>

把sorted array變成BST，我們可以用找中間點midpoint方式，先找到中間點
使用constructBST方法，把(int[]nums, int left, int right)帶入，直到if(left>right) return null;
在找到中間點後，把中間點存到node裡，接著把left, rigit更新： -node.left = constructBST(nums, left, midpoint-1); -node.right = constructBST(nums, midpoint+1, right);

左子樹中的所有節點的值都小於根節點的值。
右子樹中的所有節點的值都大於根節點的值。
左子樹和右子樹都必須是BST。


class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length ==0) return null;
        return constructBST(nums, 0, nums.length-1);
    }
    public TreeNode constructBST(int[]nums, int left, int right){
        if(left>right) return null;
        int midpoint = left + (right -left)/2; //找中間點index
        TreeNode node = new TreeNode(nums[midpoint]);
        node.left = constructBST(nums, left, midpoint-1);
        node.right = constructBST(nums, midpoint+1, right);
        return node;
    }
}

Time: O(log n)

Space: O(n)

Leetcode-108. Convert Sorted Array to Binary Search Tree

<解題>