题解 | 将升序数组转化为平衡二叉搜索树

/*class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return TreeNode类
 */
export function sortedArrayToBST(nums: number[]): TreeNode {
    // write code here
    if (nums.length === 0) return null;
    // 递归构造平衡二叉搜索树
    const buildTree= (left:number,right:number):TreeNode|null =>{
        if(left >right){
            return null;
        }
        const mid =Math.floor((left +right)/2);
        const node = new TreeNode(nums[mid]);

        node.left =buildTree(left,mid-1);
        node.right=buildTree(mid+1,right);
        return node;
    }


    return buildTree(0, nums.length - 1); // 开始构建树
}

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <cstddef>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return TreeNode类
     */
    TreeNode * creatTree(int left,int right,vector<int> nums){
        if(left>right){
            return NULL;
        }
        int mid=(left+right+1)/2;
        TreeNode *root=new TreeNode(nums[mid]);
        root->left=creatTree(left,mid-1,nums);
        root->right=creatTree(mid+1, right,nums);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        // write code here
        if(nums.size()==0) return NULL;
        return creatTree(0,nums.size()-1,nums);

    }

};