力扣108、将有序数组转换为二叉搜索树

笨方法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode *getNewNode(int val) {
    struct TreeNode *p = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    p->val = val;
    p->left = p->right = NULL;
    return p;
}
int get_hight(struct TreeNode *root) { //获取树高
    if (root == NULL) return 0;
    int l = get_hight(root->left);
    int r = get_hight(root->right);
    return (l > r ? l : r) + 1;
}
struct TreeNode *left_rotate(struct TreeNode *root) { //左旋操作 
    struct TreeNode *temp = root->right;
    root->right = temp->left;
    temp->left = root;
    return temp;
}

struct TreeNode *right_rotate(struct TreeNode *root) { //右旋操作 
    struct TreeNode *temp = root->left;
    root->left = temp->right;
    temp->right = root;
    return temp; 
}

struct TreeNode *maintain(struct TreeNode *root) {
    if (abs(get_hight(root->left) - get_hight(root->right)) <= 1) return root;
    if (get_hight(root->left) > get_hight(root->right)) { //左子树高，失衡 ,L 
        if (get_hight(root->left->right) > get_hight(root->left->left)) {
            root->left = left_rotate(root->left);  //LR失衡
        }
        root = right_rotate(root); //   LL失衡
    } else { //右子树高， 失衡 R
        if (get_hight(root->right->right) < get_hight(root->right->left)) { //  RL失衡
                root->right = right_rotate(root->right); 
            }
        root = left_rotate(root);  // RR失衡
    }
    return root;
}
struct TreeNode *insert(struct TreeNode *root, int val) {
    if (root == NULL) return getNewNode(val);
    if (root->val == val) return root;
    if (root->val > val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return maintain(root);
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    struct TreeNode *root = NULL;
    for (int i = 0; i < numsSize; i++) {
        root = insert(root, nums[i]);
    }
    return root;
}

struct TreeNode* helper(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }

    // 总是选择中间位置左边的数字作为根节点
    int mid = (left + right) / 2;

    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[mid];
    root->left = helper(nums, left, mid - 1);
    root->right = helper(nums, mid + 1, right);
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return helper(nums, 0, numsSize - 1);
}

快速方法

思路

• 对于平衡二叉树，其左子树和右子树高度绝对值不超过1
• 所以我们将有序数组对半进行划分给左右子树

代码演示1

struct TreeNode* helper(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    // 总是选择中间位置左边的数字作为根节点
    int mid = (left + right) / 2;

    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[mid];
    root->left = helper(nums, left, mid - 1);
    root->right = helper(nums, mid + 1, right);
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    return helper(nums, 0, numsSize - 1);
}

代码演示二

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode *func(int *nums, int left, int right) {
    
    if (left >= right) {
        return NULL;
    }
    int ind = (left + right) >> 1; // 选择中间位置右边的数字作为根节点
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = nums[ind];
    root->left = func(nums, left, ind);
    root->right = func(nums, ind + 1, right);
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    return func(nums, 0, numsSize);
}