主題

[LeetCode C#] 108. Convert Sorted Array to Binary Search Tree - Binary Search Tree

帥氣跳蚤蛋 | 2021-07-21 23:45:33 | 巴幣 0 | 人氣 79

難度: 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;
    }
}

創作回應

相關創作

更多創作