代码随想录算法训练营第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; }