Eisen 筆記

#108. Convert Sorted Array to Binary Search Tree

題目描述

給你一個按照升序排列的整數陣列nums，將它轉換成高度平衡二元搜尋樹。

高度平衡二元樹指的是二元樹中的每個節點的兩個子樹之間的深度不會大於1。

限制條件

  1. 1 <= nums.length <= 10^4
  2. -10^4 <= nums[i] <= 10^4
  3. nums確實地遵照升序排列。

解題思路

雖然題目把重點提示放在高度平衡上，但是要注意要轉換的目標是高度平衡二元搜尋樹，二元搜尋樹的特點是根節點的左子樹所有的節點值一定比根結點值小，右子樹所有的節點值一定比根結點值大。

換句話說，把每個子樹的值攤開成陣列來看的話，根節點的值一定位於中心。

Divide and Conquer

要解決這個問題要設計一個演算法來排序節點，我們首先要做的是找到最小的排列組合。

這邊可以讓我們從最小的幾個例子開始思考。

  1. nums.Length = 1 當陣列長度等於1時，沒有必要處理，直接轉換成節點回傳就好。
  2. nums.Length = 2 選擇較大值的為根節點，較小的值為左子節點。
  3. nums.Length = 3 取中間值為根節點，較大值為右子節點，較小值為左子節點。
  4. nums.Length = 4 取中間值為根節點，假設陣列為[0,1,2,3]，所以中間值是2，左邊會剩下[0,1]需要選擇，右邊則會剩下3，因此左邊可以重複例子2的做法，右邊則使用例子1的處理方式。
  5. nums.Length = 5 取中間值為根節點，假設陣列為[0,1,2,3,4]，所以中間值是2，左邊會剩下[0,1]需要選擇，右邊則會剩下[3,4]，左邊和右邊都可以重複例子2的做法。
  6. nums.Length = 6 取中間值為根節點，假設陣列為[0,1,2,3,4,5]，所以中間值是3，左邊會剩下[0,1,2]需要選擇，右邊則會剩下[4,5]，左邊可以重複例子3的做法，右邊則使用例子2的做法。

以此類推，可以發現到要設計的最小方法要包含處理陣列元素為1、2以及3的時候，而之後的陣列不管多長，只要不斷的去拆分，最後拆出來的最小模板都會是長度在1、2、3的時候的狀態。

public class Solution { 
	public TreeNode SortedArrayToBST(int[] nums) {
		//
        if(nums.Length==0) return null;
		//
        if(nums.Length==1) return new TreeNode(nums[0]);
		//
        int mid = nums.Length/2;        
        int[] leftPart = nums.Take(mid).ToArray();
        int[] rightPart = nums.Skip(mid+1).ToArray();		
        TreeNode head = new TreeNode(nums[mid]);
        head.left = SortedArrayToBST(leftPart);
        head.right = SortedArrayToBST(rightPart);
        return head;
    }
}

複雜度分析：

  • 時間複雜度：由於每個陣列元素都要處理，因此執行時間為N，時間複雜度為O(n)。
  • 空間複雜度：利用遞迴處理，會堆疊函式，另外還要將數值轉換成樹的節點，因此空間複雜度為O(n)。

學習重點

  • Divide and Conquer
Last Updated:
Contributors: eisen