代码随想录算法训练营第十九天|Day19二叉树

669. 修剪二叉搜索树

题目链接/文章讲解： https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解： https://www.bilibili.com/video/BV17P41177ud

思路

struct TreeNode* trimBST(struct TreeNode* root, int low, int high) {
    if (root == NULL) {
        return NULL;
    }
    if (root->val < low) {
        return trimBST(root->right, low, high);
    }
    if (root->val > high) {
        return trimBST(root->left, low, high);
    }
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}

学习反思

通过递归的方式对树进行修剪。首先判断根节点的值与范围的关系，如果根节点的值小于范围的下限 low，就递归修剪右子树，返回右子树作为修剪后的树的根节点；如果根节点的值大于范围的上限 high，就递归修剪左子树，返回左子树作为修剪后的树的根节点；如果根节点的值在范围内，就递归修剪左右子树，并更新根节点的左右子节点为修剪后的左右子树。最后返回根节点。时间复杂度是 O(N)。

108.将有序数组转换为二叉搜索树

题目链接/文章讲解：

https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1uR4y1X7qL

思路

struct TreeNode* sortedArrayToBSTHelper(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    int mid = left + (right - left) / 2; 
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); 
    root->val = nums[mid]; 
    root->left = sortedArrayToBSTHelper(nums, left, mid - 1); 
    root->right = sortedArrayToBSTHelper(nums, mid + 1, right); 
    return root; 
}

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

学习反思

将一个有序数组转换为一棵平衡二叉搜索树的函数实现。函数的思路是通过递归的方式，每次取数组的中间值作为根节点，并以中间值为分界点将数组分为左右两部分，然后分别递归构建左子树和右子树。时间复杂度是O(n)。

538.把二叉搜索树转换为累加树

题目链接/文章讲解：

https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1d44y1f7wP

思路

void convertBSTHelper(struct TreeNode* node, int* sum) {
    if (node == NULL) {
        return;
    }
    convertBSTHelper(node->right, sum);
    *sum += node->val;
    node->val = *sum;
    convertBSTHelper(node->left, sum);
}

struct TreeNode* convertBST(struct TreeNode* root) {
    int sum = 0; 
    convertBSTHelper(root, &sum);
    return root; 
}