主題
難度: Easy
===========================================================================
說明:
給予一按遞增排序的陣列,將之轉(zhuǎn)換為"高度平衡"的二元搜索樹,
"高度平衡"的二元搜索樹表示,各節(jié)點(diǎn)的兩子樹深度不超過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. 左子樹節(jié)點(diǎn)上的所有數(shù)值皆小於根結(jié)點(diǎn)的數(shù)值
2. 右子樹節(jié)點(diǎn)上的所有數(shù)值皆大於根結(jié)點(diǎn)的數(shù)值
3. 任意節(jié)點(diǎn)的左右子樹皆須符合1,2的定義
4. 不存在任何數(shù)值相等的節(jié)點(diǎn)
因此採用二元搜尋來產(chǎn)生二元搜索樹,
首先將該陣列的中間值作為整個樹的根結(jié)點(diǎn),
採用遞迴分別建立左右節(jié)點(diǎn)
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) //若左指針大於右指針表示超過搜索範(fàn)圍
return null;
int middle = left + (right - left) / 2; //取得中間指標(biāo)值
TreeNode node = new TreeNode(nums[middle]); //創(chuàng)建一個節(jié)點(diǎn)並寫入中間值
node.left = Build(nums, left, middle - 1); //左節(jié)點(diǎn),左指標(biāo)不動,右指標(biāo)左移
node.right = Build(nums, middle + 1, right); //右節(jié)點(diǎn),左指標(biāo)右移,右指標(biāo)不動
return node;
}
}
達(dá)人
