LeetCode: 108. Convert Sorted Array to Binary Search Tree 解題紀錄

Last Updated on 2024-11-25 by Clay

題目

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 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:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

---

解題思路

這題要求的是將一個升序排列的陣列組成高度平衡的二元樹，我採用的解題方式是使用遞迴，每次都會取得陣列最中央的數值組成節點，然後把該中心節點的左子樹指向左邊區域的遞迴返回結果、右子樹指向右邊區域的遞迴返回結果 —— 依此類推，到最後就會自動組成一個高度平衡的二元樹。

C++ 範例程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* DFS(vector<int>& nums, int left, int right) {
        // Base case
        if (left > right) {
            return nullptr;
        }

        // Get middle node
        int mid = (left + right) / 2;
        TreeNode* node = new TreeNode(nums[mid]);

        // Get both sides nodes
        node->left = DFS(nums, left, mid-1);
        node->right = DFS(nums, mid+1, right);

        return node;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return DFS(nums, 0, nums.size()-1);
    }
};

Python 範例程式碼

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def dfs(self, nums: List[int], left: int, right: int) -> Optional[TreeNode]:
        # Base case
        if left > right:
            return None

        # Get middle node
        mid = (left + right) // 2
        node = TreeNode(val=nums[mid])

        # Get both sides nodes
        node.left = self.dfs(nums=nums, left=left, right=mid-1)
        node.right = self.dfs(nums=nums, left=mid+1, right=right)

        return node

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        return self.dfs(nums=nums, left=0, right=len(nums)-1)

---

References

• https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/submissions/1462520698/?envType=problem-list-v2&envId=tree

---

Read More

• LeetCode 解題紀錄目錄