代码随想录算法训练营第22天-leetcode-二叉树08：669. 修剪二叉搜索树；108.将有序数组转换为二叉搜索树；538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

力扣题目链接(opens new window)

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

分析：

需要遍历整棵树，因为父节点被删除或者保留，子节点都有可能删除或者保留；父节点被删除时，左子树和右子树只可能保留一个

我的做法：

后序遍历每个节点，对于在范围外的节点，考虑保留其左子树/右子树（只可能保留一个）

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

代码随想录：

全部写成递归

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

 

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

力扣题目链接(opens new window)

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

分析：

不断选取中点！

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

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

力扣题目链接(opens new window)

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。

分析：

二叉搜索树——中序排序

题目要求，实际上是每个节点加上中序排列后面的那个节点，故而可以反向中序排序，即RNL，用prior记录前一个节点的值，加上前一个节点的值即可

void build(struct TreeNode*root,int* prior){
    if(root==NULL) return ;
    build(root->right,prior);
    root->val=root->val+*prior;
    *prior=root->val;
    build(root->left,prior);
 
}
struct TreeNode* convertBST(struct TreeNode* root) {
    int prior=0;
    build(root,&prior);
    return root;
}