主題
難度: Easy
===========================================================================
說明:
給予一按遞增排序的陣列,將之轉換為"高度平衡"的二元搜索樹,
"高度平衡"的二元搜索樹表示,各節點的兩子樹深度不超過1
===========================================================================
測資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:
測資2:
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are both a height-balanced BSTs.
===========================================================================
條件限制:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums陣列按遞增的順序排序
===========================================================================
解題:
本題要建立二元搜索樹,而二元搜索樹成立的必要條件為:
1. 左子樹節點上的所有數值皆小於根結點的數值
2. 右子樹節點上的所有數值皆大於根結點的數值
3. 任意節點的左右子樹皆須符合1,2的定義
4. 不存在任何數值相等的節點
因此採用二元搜尋來產生二元搜索樹,
首先將該陣列的中間值作為整個樹的根結點,
採用遞迴分別建立左右節點
public class Solution
{
public TreeNode SortedArrayToBST(int[] nums)
{
return Build(nums, 0, nums.Length - 1); //採用遞迴,二元搜尋建立二元搜索樹
}
public TreeNode Build(int[] nums, int left,int right)
{
if (left > right) //若左指針大於右指針表示超過搜索範圍
return null;
int middle = left + (right - left) / 2; //取得中間指標值
TreeNode node = new TreeNode(nums[middle]); //創建一個節點並寫入中間值
node.left = Build(nums, left, middle - 1); //左節點,左指標不動,右指標左移
node.right = Build(nums, middle + 1, right); //右節點,左指標右移,右指標不動
return node;
}
}
達人
