LeetCode 108. Convert Sorted Array to Binary Search Tree [Easy] [C++] 解題筆記

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

想法:

    類似 binary search 的技巧，每次選取中間的值作為 root，然後將左右邊剩下的值繼續遍歷，

在左右邊的 sub array 中找出左子樹與右子樹的 root。

完整程式碼:

class Solution {
public:
    TreeNode* constructBST(vector<int>& nums, int left, int right) {
        if (left > right) { return nullptr; }
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = constructBST(nums, left, mid - 1);
        root->right = constructBST(nums, mid + 1, right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) { return nullptr; }
        return constructBST(nums, 0, nums.size() - 1);
    }
};