Leecode 530. 二叉搜索树的最小绝对差

链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

直接按照中序遍历的顺序利用后者减去前者更新不同节点值之间的最小差值

 // 我们只要按照前序遍历然后逐个比较前后节点的差值就OK了，并用一个变量记住当前节点差的最小值
class Solution {
public:int res = INT_MAX; // 保证是中序遍历中的后面节点减去当前节点，所以-1其实是非法值，是一定会被更新的TreeNode *pre = NULL;void recursion(TreeNode *root){if(root == NULL) return;// 开始的时候先向左递归recursion(root -> left);if(pre != NULL) res = min(res,root -> val - pre -> val);pre = root;recursion(root -> right);}int getMinimumDifference(TreeNode* root) {recursion(root);return res;}
};

Leecode 501.二叉搜索树中的众数

链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/

一看就是要用到容器。直观想法就是用哈希表对二叉树搜索一遍，然后对其中的元素进行处理

class Solution {
public:unordered_map m;bool static cmp(const pair& s1,const pair& s2){return s1.second > s2.second; // 对second也就是该数字出现的次数进行排序}  void recursion(TreeNode* root){// 如果是空值就直接返回if(root == NULL) return;// 只要不是空值就直接记录，我们这里使用的是中序遍历，其实什么遍历顺序都是OK的m[root -> val]++;recursion(root -> left);recursion(root -> right);}vector findMode(TreeNode* root) {// 首先把所有节点都加入到哈希表中，然后利用这个哈希表新创建一个vector// 然后对vector进行排序然后输出，这样其实并没有要求递归顺序recursion(root); vector>vec (m.begin(),m.end()); // 注意vector是怎么接哈希表的vector res;sort(vec.begin(),vec.end(),cmp);int number = vec[0].second;for(int i=0;iif(vec[i].second == number) res.push_back(vec[i].first);}return res;}
};

leecode 236. 二叉树的最近公共祖先

链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

注意一个细节：我们是如何处理最近公共祖先是p或者q的？

这里假设我们在遍历二叉树的时候先搜到了q，那么有两种情况：

1. p在q的子树上，也就是二者的最近公共祖先就是q
2. p不在q的子树上

显然不论哪种情况，我们都应该直接返回q，第一种情况对应着在q的父节点的另外一侧搜不到p；第二种情况对应着在q的下面继续搜索是无效的

那么显然，遇见q或者p我们就应该直接返回！

剩余情况是没有搜到q或者p，我们就应该继续递归当前节点的左右子树

那么应该如何return呢？

1. 如果左右节点都不为空，此时p和q分别在当前节点的左右子树上，所以应该返回root
2. else 如果左节点不为空返回左节点，else 如果右节点不为空返回右节点
3. else 直接返空值

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 看见题目给我们的函数的返回值就是指针，所以我们可以直接用if(root == NULL || root == p || root == q) return root;root -> left =  lowestCommonAncestor(root -> left,p,q);root -> right = lowestCommonAncestor(root -> right,p,q);if(root -> left != NULL && root -> right != NULL) return root ;if(root -> left != NULL) return root -> left;if(root -> right != NULL) return root -> right;return NULL;}
};

Leecode 235. 二叉搜索树的最近公共祖先

链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

还是返回公共祖先，但是环境是二叉搜索树，那么我们就能对上面的代码进行优化

1. 若当前节点的值同时大于p和q的值，那么我们就往其左子树搜索
2. 若当前节点的值同时小于p和q的值，那么我们就往其右子树搜索
3. 若当前节点的值恰好位于p和q中间，那么这个节点就是二者的最近公共祖先，因为不论是向左还是向右递归都会导致这个性质消失，而只有公共祖先才满足值位于左子树和右子树中间这个性质

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 看见当前函数的返回值就是指针，因此我们直接在这个函数上面写递归if(root == NULL) return root;if((root -> val > p->val && root -> val < q->val) || (root -> val < p->val && root -> val > q->val)) return root;if(root -> val > p->val && root -> val > q->val) {root -> left =  lowestCommonAncestor(root -> left,p,q); if(root -> left != NULL) return root -> left;}if(root -> val < p->val && root -> val < q->val) {root -> right = lowestCommonAncestor(root -> right,p,q);if(root -> right != NULL) return root -> right;}// 因为递归左右子树是选择性的，也就是说不一定去递归，那么我们在递归完毕后判断：若是没有返回空，那么我们就直接返回return root;}
};

这种写法其实还是有一些细节的。根据我们前面描述的，一共会有四种情况：当前节点是空节点；当前节点由于值位于p和q之间故一定是最近公共祖先；当前节点是p；当前节点是q

1. 首先判断当前节点是不是空节点，若是空节点直接返回空就完事了
2. 其次判断当前节点的值是不是位于q和p之间，若是，那么当前节点一定是最近公共祖先，直接返回就OK
3. 若不是，那么接下来看p和q是位于当前节点的左子树还是右子树上面，然后分情况递归
4. 若都不是，那么当前节点一定是p或q之一，直接返回当前节点就OK

为什么左节点有值或者右节点有值就一定可以返回呢？因为当前节点肯定不是最近公共祖先，才会去分别递归左右子树

按照这个逻辑，我们还可以进一步优化——如果当前节点就是最近公共祖先，那么一定不满足递归左右子树的条件，所以会直接return root，故我们其实也不需要判断当前节点的值是不是位于左右子树中间，简化代码如下：

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == NULL) return root;if(root -> val > p->val && root -> val > q->val) {root -> left =  lowestCommonAncestor(root -> left,p,q); if(root -> left != NULL) return root -> left;}if(root -> val < p->val && root -> val < q->val) {root -> right = lowestCommonAncestor(root -> right,p,q);if(root -> right != NULL) return root -> right;}return root;}
};

Leecode 701.二叉搜索树中的插入操作

链接：https://leetcode.cn/problems/insert-into-a-binary-search-tree/

仔细分析题意我们意识到可以直接插入到叶子节点上面而不需要改变其他节点的结构

因为是二叉搜索树，所以我们是有方向地递归，所以递归到的空值都是符合题意的

那么我们直接递归就好了呀

但是如何处理递归的终止条件呢？因为若是当前节点为空，并不容易把握到当前节点的上一个节点是什么

因为插入一次就完事，所以我们考虑在递归之前就插入（若递归的目标是空），插入后就把flag置1

这样终止条件就是if(flag)，也就是插入完毕以后直接递归

所以递归函数也不要返回值

class Solution {
public:int flag = 0;void recursion(TreeNode* &root,int val){if(flag) return;// 可以考虑先插入，后递归if(val > root -> val) {if(root -> right == NULL) {root -> right = new TreeNode(val);flag = 1;return;} recursion(root -> right,val);}if(val < root -> val) {if(root ->  left == NULL) {root -> left  = new TreeNode(val);flag = 1;return;} recursion(root -> left,val); } // 如果当前子节点不为空，那么就不能直接插入，我们继续递归        }TreeNode* insertIntoBST(TreeNode* root, int val) {// 我们还是直接递归，但是返回值是指针吗？// 其实插入之后就不需要什么返回值了，因为是单步的操作，所以我们可以设置一个flag函数，插入完成后就设置成1，然后直接return就完事了if(root == NULL) {root = new TreeNode(val);return root;}recursion(root,val);return root;}
};

Leecode 450. 删除二叉搜索树中的节点

链接：https://leetcode.cn/problems/delete-node-in-a-bst/

首先要把返回值给想好，返回值不合适题目就异常难做，然后就是考虑好所有情况，之后就蛮容易A的

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {// 首先我们要想好删除节点的所有情况// 最简单的情况就是要删除的节点是叶子节点，但是即使是最简单的情况，删除之后我们也要其父亲指向空而不能再指向这个被删除的节点// 很容易想到的一种想法就是维护当前节点的前面一个节点，但是这样很费劲，代码也特别难写，所以我们考虑直接让函数返回指针，然后我们递归调用当前的节点的左右子树// 这样删除之后左右子树向上return就可以直接把合法的节点返回给其父亲// 因为我们递归的时候没有判空，所以要把遇到空节点的情况写出来if(root == NULL) return NULL;// 先把删除叶子节点的情况给写出来if(root -> val == key){if(root -> left == NULL && root -> right == NULL){delete root;return NULL;}// 我们接着考虑删除节点的其他情况// 当前节点只有一条分支，也就是说当前节点只有左子树或者右子树else if(root -> left != NULL && root -> right == NULL){TreeNode* cur = root->left;delete root;return cur;}else if(root -> right != NULL && root -> left == NULL){TreeNode* cur = root->right;delete root;return cur;}// 此时左右节点都不为空，其实有两种拼接方式：把左儿子接上去然后把左儿子下面最大的节点的右侧接上当前节点的右儿子；或者是把右儿子接上去并且把右儿子下面最小的节点的左侧接上当前节点的左儿子，我们选择一种方法就可，这里选择第一种else{TreeNode* cur = root -> left;TreeNode* tar = cur;while(tar -> right!=NULL) tar = tar -> right;tar -> right = root -> right;delete root;return cur;}}// 如果当前节点不是目标节点，那么就朝合适的方向递归if(root -> val > key) root -> left =  deleteNode(root -> left, key);if(root -> val < key) root -> right = deleteNode(root -> right,key);// 因为题目要求返回头节点，所以直接返回头节点就OKreturn root;}
};

Leecode 669. 修剪二叉搜索树

链接：https://leetcode.cn/problems/trim-a-binary-search-tree/

此题和前面两题有明显的区别：之前两个题目都是删除一个节点，这个题目是删除“一些”节点

所以我们return的时机需要把握一下：

1. 刚开始的时候若是遇到了空节点，我们就直接return NULL
2. 接下来我们处理值不位于区间内的情况，其实和上一题很类似，删除的节点有很多种情况…但是我们不能直接返回当前节点，因为不能保证后面节点都符合题意，所以要return 递归函数

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {// 因为需要删除“一些节点”，所以我们返回值的时机需要改变// 那么是返回指针吗？修改节点之后返回指针是相对容易的做法if(root == NULL) return NULL;// 接下来看不合法情况的返回值if(root -> val > high || root -> val < low){ if(root -> left == NULL && root -> right == NULL) return NULL;else if(root -> left != NULL && root -> right == NULL) return trimBST(root -> left, low,high);else if(root -> right != NULL && root -> left == NULL) return trimBST(root -> right,low,high);else{if(root -> val > high) return trimBST(root -> left,low,high);else return trimBST(root -> right,low,high);}}root -> left =  trimBST(root -> left,low,high);root -> right = trimBST(root -> right,low,high);return root;}
};

但是我们中间的一大段逻辑其实都可以两行搞定

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

因为如果当前节点的值大于了high，那么右子树全都pass；同理如果当前的值小于low，那么左子树的值全都pass，也就是说我们直接返回递归就好，不需要考虑那么多复杂的情况

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

链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

这道题其实比之前做的“利用后序数组和中序数组构建二叉树”要简单很多

首先找到中间节点令其作为当前数组的根节点，然后划分数组左右递归建树就完事了

递归结束条件还是：当前数组为空

class Solution {
public:TreeNode* sortedArrayToBST(vector& nums) {// 递归建树，找见中间节点后划分数组，然后分别递归if(nums.size() == 0) return NULL;int mid = (int)nums.size()/2;TreeNode* cur = new TreeNode(nums[mid]);// 开始划分数组vector nums1 (nums.begin(),nums.begin() + mid);vector nums2 (nums.begin() + mid + 1,nums.end());cur -> left = sortedArrayToBST(nums1);cur -> right = sortedArrayToBST(nums2);return cur;}
};

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

链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/

这道题我首先想到的是返回值为int，尝试了一番发现很难做…

为什么难做？因为有返回值基本上就需要接住返回值

我们一般都是递归左子树和递归右子树吧，那么是根节点接住返回值吗？

if(root -> right != NULL) root ->  val += recursion(root->right); 
if(root -> left != NULL) root -> val += recursion(root->left); 

这样肯定是错的吧，照这样写中间节点的值反而是最大的，按照题意应该是左侧的节点值最大

所以我们需要重新思考返回值，也要开始思考遍历的顺序

右侧节点是最先开始遍历的，然后更新中间节点，然后更新中间节点的左子树…

所以遍历顺序其实是：右 -> 中 -> 左

要实现这种遍历顺序，我们就不能要返回值

我们用递归实现就简单很多

class Solution {
public:int sum = 0;void recursion(TreeNode* root){if(root == NULL) return;// 先递归右侧recursion(root -> right);// 递归完毕之后往上return更新节点值sum += root -> val;root -> val = sum;// 如果当前节点有左子树，那么再遍历左子树recursion(root -> left);}TreeNode* convertBST(TreeNode* root) {int sum = 0;recursion(root);return root;}
};

二叉树淦完了！欢呼~