題目連結

題型解說

這是一題難度為簡單的題目

需要設計一個方法，此方法會傳入一個排序好的陣列 nums

回傳一顆平衡的二元搜尋樹，左右兩邊的層級不能超過 1

解題思路

二元搜尋樹有幾個特性

1. 不會有重複的值
2. 左節點數值一定比根節點數值小
3. 右節點數值一定比根節點數值大
4. 其他層的節點也要符合以上要求

既然所有的右邊節點一定比根節點大，所有左邊節點一定比根節點小，題目也規定兩邊的層數不能相差超過 1

那麼根節點只能選 nums 的中間值，這邊有個小疑問「如果 nums 是偶數呢?」，是要選左邊那個還是右邊那個？

答案其實無所謂，因為題目有提示說答案不止一種

根節點選擇好了後就能把 nums 拆成左右兩部分，左右兩部分也需要符合 二元搜尋樹 的特性

那一樣選擇中間值拆左右兩部分，所以分析後最適合的解法就是二分搜尋法了

程式碼

Java

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        
        return sortedArrayToBST(nums, 0, nums.length);
    }
    
    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left == right) {
            return null;
        }
        
        int mid = (left + right) /2;
        
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBST(nums, left, mid);
        node.right = sortedArrayToBST(nums, mid +1, right);
        
        return node;
    }
}

class Solution { // 其他人的二分搜尋法
    public TreeNode sortedArrayToBST(int[] nums) {
		int length = nums.length;
		return generateTree(nums, 0, length - 1);
	}

	private TreeNode generateTree(int[] nums, int low, int high) {
		if (low > high) {
			return null;
		}
		int mid = low + (high - low) / 2;
		TreeNode root = new TreeNode(nums[mid]);
		root.left = generateTree(nums, low, mid - 1);
		root.right = generateTree(nums, mid + 1, high);
		return root;
	}
}