2023年7月9日发(作者：)

【⼆叉树3--⼆叉搜索树】BST基本操作+相应题⽬+扩展前⾔/⽬录前⽂已经写了【⼆叉树基本框架&常规题⽬】+ 【多种⽅式序列化和反序列化⼆叉树⽅法】本篇⽂章将记录和写⼀下⼆叉树中常考的⼆叉搜索树的基础、题⽬和扩展题⽬（101）。定义及操作集锦⾸先，BST 的特性⼤家应该都很熟悉了：1、对于 BST 的每⼀个节点node，左⼦树节点的值都⽐node的值要⼩，右⼦树节点的值都⽐node的值⼤。2、对于 BST 的每⼀个节点node，它的左侧⼦树和右侧⼦树都是 BST。⼆叉搜索树并不算复杂，但我觉得它构建起了数据结构领域的半壁江⼭，直接基于 BST 的数据结构有 AVL 树，红⿊树等等，拥有了⾃平衡性质，可以提供 logN 级别的增删查改效率；还有 B+ 树，线段树等结构都是基于 BST 的思想来设计的。关于BST的构建合法性检查、搜索或查找⼀个数是否存在、BST插⼊⼀个数、BST删除⼀个数【构建、改查、增、删】struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};/** * @Description:

检测BST的构造是否合法 * @param {TreeNode} *root * @return {*} * @notes:

*/boolean isValidBST(TreeNode* root){ return isValidBST(root, nullptr, nullptr);}boolean isValidBST(TreeNode* root,TreeNode* min, TreeNode* max){ //

辅助函数 ——

检测是否构成合法的BST if(root == nullptr) return true; //

注意当前节点要和所有的左右节点⽐较！ if(min != nullptr && root->val <= min->val) return false; if(max != nullptr && root->val >= max->val) return false; //

其它交给递归 return isValidBST(root->left, min, root) && isValidBST(root->right, root, max); //

相当于在后⾯给所有节点添加了⼀个 min

和 max的边界约束。 //

约束了root

的左⼦树节点值不超过root的值、右⼦树节点值不⼩于root的值。}/** * @Description:

搜索、改查 * @param {*} * @return {*} * @notes:

*/boolean isInBST(TreeNode* root, int target){ //

当前节点该做的事 if(root == nullptr) return false; if(root->val == target) return true; //

递归框架. //

递归框架. if(target > root->val) return isInBST(root->right, target); if(target < root->val) return isInBST(root->left, target);}/** * @Description:

增（插⼊） * @param {*} * @return {*} * @notes:

*/TreeNode* insertIntoBST(TreeNode* root, int val){ //

新增节点，所以要返回构建的节点 if(root == nullptr) return new TreeNode(val);

if(val == root->val) return root; //

重复了不添加新的 else if(val > root->val){ root->right = insertIntoBST(root->right, val); }else if(val < root->val){ root->left = insertIntoBST(root->left, val); } return root;}/** * @Description:

最复杂和难的

* @param {*}

注意关键：按照有⼏个⼦节点进⾏分类和

构建伪代码框架——分为三类;

且注意：两个节点要找到最⼩的进⾏互换之后、删除最⼩的节点即可。 * @return {*} * @notes:

*/TreeNode* deleteNode(TreeNode* root, int key){ //

⾸先搜索，找到了分情况删除；

未找到递归查找。 if(root == nullptr ) return nullptr; if(root->val == key){ //

分情况进⾏删除结点；三种情况。 //

⼀ if(root->left == nullptr && root->right == nullptr) return nullptr; //

⼆

（可以和上⼀种合起来 if(root->left == nullptr) return root->right; if(root->right == nullptr) return root->left; //

第三种情况： //

先找到最⼩的节点赋值，

然后递归删除最后的节点即可。 TreeNode* cur_min = getMin(root->right); //

这⾥决定了选择右边最⼩的节点进⾏交换 //

声明这样做不正规，但是正确；（本应该是在指针级别

进⾏操作的；因为不同结构体内的成员不同 root->val = cur_min->val; // return deleteNode(root->right, cur_min->val); //

错了 root->right = deleteNode(root->right, cur_min->val); //【这样才对，否则

就覆盖了root了！】 }else if(root->val > key){ root->left = deleteNode(root->left, key); }else if(root->val < key){ root->right = deleteNode(root->right, key); } return root;}TreeNode* getMin(TreeNode* root){ //

辅助函数——辅助第三种情况交换节点

并删除 //

要么右边最⼩节点；

要么左边最⼤节点 //

这⾥选择右边最⼩节点 [只能上⼀层

主函数进⾏选择] while(root->left != nullptr) root = root->left; return root;}性质从做算法题的⾓度来看 BST，除了它的定义，还有⼀个重要的性质：BST 的中序遍历结果是有序的（升序）。也就是说，如果输⼊⼀棵 BST，以下代码可以将 BST 中每个节点的值升序打印出来：void traverse(TreeNode root) { if (root == null) return; traverse(); //

中序遍历代码位置 print(); traverse();}但是注意区分——普通搜索遍历 和 构建Tree的遍历：/** * @Description:

搜索、改查 * @param {*} * @return {*} * @notes:

*/boolean isInBST(TreeNode* root, int target){ //

当前节点该做的事 if(root == nullptr) return false; if(root->val == target) return true; //

递归框架. if(target > root->val) return isInBST(root->right, target); if(target < root->val) return isInBST(root->left, target);}/** * @Description:

增（插⼊） * @param {*} * @return {*} * @notes:

*/TreeNode* insertIntoBST(TreeNode* root, int val){ //

新增节点，所以要返回构建的节点 if(root == nullptr) return new TreeNode(val);

if(val == root->val) return root; //

重复了不添加新的 else if(val > root->val){ root->right = insertIntoBST(root->right, val); }else if(val < root->val){ root->left = insertIntoBST(root->left, val); } return root;}刷题1 LeetCode230 & 538(1038)描述那么根据这个性质，我们来做两道算法题。（⽐较简单不再赘述，只谈⼀些【提升之处】）T230 BST寻找第k⼩的值中：这道题就做完了，不过呢，还是要多说⼏句，因为这个解法并不是最⾼效的解法，⽽是仅仅适⽤于这道题。dong’s 旧⽂ 中就提过今天的这个问题：如果让你实现⼀个在⼆叉搜索树中通过排名计算对应元素的⽅法select(int k)，你会怎么设计？如果按照我们刚才说的⽅法，利⽤「BST 中序遍历就是升序排序结果」这个性质，每次寻找第k⼩的元素都要中序遍历⼀次，最坏的时间复杂度是O(N)，N是 BST 的节点个数。要知道 BST 性质是⾮常⽜逼的，像红⿊树这种改良的⾃平衡 BST，增删查改都是O(logN)的复杂度，让你算⼀个第k⼩元素，时间复杂度竟然要O(N)，有点低效了。所以说，计算第k⼩元素，最好的算法肯定也是对数级别的复杂度，不过这个依赖于 BST 节点记录的信息有多少。我们想⼀下 BST 的操作为什么这么⾼效？就拿搜索某⼀个元素来说，BST 能够在对数时间找到该元素的根本原因还是在 BST 的定义⾥，左⼦树⼩右⼦树⼤嘛，所以每个节点都可以通过对⽐⾃⾝的值判断去左⼦树还是右⼦树搜索⽬标值，从⽽避免了全树遍历，达到对数级复杂度。那么回到这个问题，想找到第k⼩的元素，或者说找到排名为k的元素，如果想达到对数级复杂度，关键也在于每个节点得知道他⾃⼰排第⼏。⽐如说你让我查找排名为k的元素，当前节点知道⾃⼰排名第m，那么我可以⽐较m和k的⼤⼩：1、如果m == k，显然就是找到了第k个元素，返回当前节点就⾏了。2、如果k < m，那说明排名第k的元素在左⼦树，所以可以去左⼦树搜索第k个元素。3、如果k > m，那说明排名第k的元素在右⼦树，所以可以去右⼦树搜索第k - m - 1个元素。这样就可以将时间复杂度降到O(logN)了。那么，如何让每⼀个节点知道⾃⼰的排名呢？这就是我们之前说的，需要在⼆叉树节点中维护额外信息。每个节点需要记录，以⾃⼰为根的这棵⼆叉树有多少个节点。也就是说，我们TreeNode中的字段应该如下：class TreeNode { int val; //

以该节点为根的树的节点总数 int size; TreeNode left; TreeNode right;}有了size字段，外加 BST 节点左⼩右⼤的性质，对于每个节点node就可以通过推导出node的排名，从⽽做到我们刚才说到的对数级算法。当然，size字段需要在增删元素的时候需要被正确维护，⼒扣提供的TreeNode是没有size这个字段的，所以我们这道题就只能利⽤ BST 中序遍历的特性实现了，但是我们上⾯说到的优化思路是 BST 的常见操作，还是有必要理解的。刷题2(45070170098)450.删除⼆叉搜索树中的节点（Medium）701.⼆叉搜索树中的插⼊操作（Medium）700.⼆叉搜索树中的搜索（Easy）98.验证⼆叉搜索树（Medium）参见开头的 基础操作集锦。【重点关注- 构建（98） + 删除（450）】构建合法性⼀、判断 BST 的合法性这⾥是有坑的哦，我们按照刚才的思路，每个节点⾃⼰要做的事不就是⽐较⾃⼰和左右孩⼦吗？看起来应该这样写代码：boolean isValidBST(TreeNode root) { if (root == null) return true; if ( != null && <= ) return false; if ( != null && >= ) return false; return isValidBST() && isValidBST();}但是这个算法出现了错误，BST 的每个节点应该要⼩于右边⼦树的所有节点，下⾯这个⼆叉树显然不是 BST，因为节点 10 的右⼦树中有⼀个节点 6，但是我们的算法会把它判定为合法 BST：出现问题的原因在于，对于每⼀个节点root，代码值检查了它的左右孩⼦节点是否符合左⼩右⼤的原则；但是根据 BST 的定义，root的整个左⼦树都要⼩于，整个右⼦树都要⼤于。【注意这⾥ 强调左右⼦树反过来对 root；即： root 对左右⼦树整体的 影响—— 所以需要整体上可以添加 参数传递。】问题是，对于某⼀个节点root，他只能管得了⾃⼰的左右⼦节点，怎么把root的约束传递给左右⼦树呢？请看正确的代码：class Solution {public: /** * @Description:

总的思路：使得中间的值⼤于所有左边

⼩于左右右边。 * @param {*}

新函数--有最⼩节点和最⼤节点

；

* @return {*} * @notes:

*/ bool isValidBST(TreeNode* root) { // if(root == nullptr) return true; return isValidBST(root, nullptr, nullptr); } //

辅助函数判断是否

⼤于和⼩于 /** * @Description:

变相后序：使得左⼦树限定在不⼤于root，

右⼦树限定在不⼩于root * @param {*}

即：左⼦树

⼩于root，

右⼦树

⼤于root； * @return {*} * @notes:

*/ bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max){ if(root == nullptr ) return true; //

三种---

使得当前节点-不超过右⼦树min[就是root节点啊！]

⼤于左⼦树max[就是root节点啊] if(min!=nullptr && root->val <= min->val) return false; if(max!=nullptr && root->val >= max->val) return false; return isValidBST(root->left, min, root)

&& isValidBST(root->right, root, max); } /** * @Description:

站在了

中间节点⾓度，上边是站在了

左右⼦树⾓度。 * @param {*} * @return {*} * @notes:

*/ bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max){ if(root == nullptr) return true; //

左搜---右边最⼩的 bool left = isValidBST(root->left, min, root); bool right = isValidBST(root->right, root, max); if(max!=nullptr && root->val >= max->val) return false; if(min!=nullptr && root->val <= min->val) return false; return left && right;};我们通过使⽤辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给⼦树的所有节点，这也是⼆叉树算法的⼀个⼩技巧吧。删除这个问题稍微复杂，跟插⼊操作类似，先「找」再「改」，先把框架写出来再说：TreeNode deleteNode(TreeNode root, int key) { if ( == key) { //

找到啦，进⾏删除 } else if ( > key) { //

去左⼦树找 = deleteNode(, key); } else if ( < key) { //

去右⼦树找 = deleteNode(, key); } return root;}找到⽬标节点了，⽐⽅说是节点A，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。有三种情况，⽤图⽚来说明。情况 1：A恰好是末端节点，两个⼦节点都为空，那么它可以当场去世了。if ( == null && == null) return null;情况 2：A只有⼀个⾮空⼦节点，那么它要让这个孩⼦接替⾃⼰的位置。//

排除了情况 1

之后if ( == null) return ;if ( == null) return ;情况 3：A有两个⼦节点，⿇烦了，为了不破坏 BST 的性质，A必须找到左⼦树中最⼤的那个节点，或者右⼦树中最⼩的那个节点来接替⾃⼰。我们以第⼆种⽅式讲解。if ( != null && != null) { //

找到右⼦树的最⼩节点 TreeNode minNode = getMin(); //

把 root

改成 minNode = ; //

转⽽去删除 minNode = deleteNode(, );}三种情况分析完毕，填⼊框架，简化⼀下代码：TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; if ( == key) { //

这两个 if

把情况 1

和 2

都正确处理了 if ( == null) return ; if ( == null) return ; //

处理情况 3 TreeNode minNode = getMin(); = ; = deleteNode(, ); } else if ( > key) { = deleteNode(, key); } else if ( < key) { = deleteNode(, key); } return root;}TreeNode getMin(TreeNode node) { // BST

最左边的就是最⼩的 while ( != null) node = ; return node;}

删除操作就完成了。注意⼀下，这个删除操作并不完美，因为我们⼀般不会通过 = 修改节点内部的值来交换节点，⽽是通过⼀系列略微复杂的链表操作交换root和minNode两个节点。因为具体应⽤中，val域可能会是⼀个复杂的数据结构，修改起来⾮常⿇烦；⽽链表操作⽆⾮改⼀改指针，⽽不会去碰内部数据。不过这⾥我们暂时忽略这个细节，旨在突出 BST 基本操作的共性，以及借助框架逐层细化问题的思维⽅式。我的解法：class Solution {public: /** * @Description:

删除节点三种情况：①叶⼦节点直接删除 ②单独节点删除并返回有的

⼀个节点 ③中间节点找到最⼩值

替换并递归删除 * @param {*} * @return {*} * @notes:

*/ TreeNode* deleteNode(TreeNode* root, int key) { if(root == nullptr) return nullptr; //

如果是当前值 ——

再分三种情况。 if(root->val == key) { // 1 if(root->left==nullptr && root->right == nullptr) return nullptr; // 2 if(root->left == nullptr) return root->right; //

上述简化了，1&2

可共⽤，删除1

；也可以！ if(root->right == nullptr) return root->left; // 3 ;

找到右边最⼩的节点替换，并递归删除叶⼦结点 int tmp = root->val; root->val = getMin(root->right, tmp); root->right = deleteNode(root->right, tmp); } if(key < root->val) root->left = deleteNode(root->left, key); else if(key > root->val) root->right = deleteNode(root->right, key); return root; } //

辅助函数寻找当前bst的最⼩值，最左边！ int getMin(TreeNode* root, int val){ while(root->left != nullptr) root = root->left; int tmp = root->val; root->val = val; return tmp; }};【必】(区别构建)拓展题⽬–递归&指针引⽤ 拓展题⽬：我的题解：class Solution{public: /** * @Description:

找到并

交换恢复BST;且

只有⼀处错误 * @param {*} * @return {*} * @notes:

*/ void recoverTree(TreeNode *root) { TreeNode *max= nullptr; TreeNode *min= nullptr; TreeNode *pre= nullptr; bool found = false; findRecover(root, pre, max, min, found); cout << max->val << endl; cout << min->val << endl; swap(max->val, min->val); } /** * @Description:

* @param {bool} isFound * @return {*} * @notes:

*/ void findRecover(TreeNode *root, TreeNode* &pre, TreeNode* &max, TreeNode* &min, bool &isFound) { if (root == nullptr) return; findRecover(root->left, pre, max, min, isFound); cout << "isFound is :" << isFound << endl;

//

中序遍历 if (pre!=nullptr && !isFound && root->val <= pre->val) { isFound = true; //

发现过⼀次错乱。 max = pre; min = root; // pre = root; // return ; cout << max -> val << endl; cout << min->val << endl; } else if (pre!=nullptr && isFound && root->val <= pre->val) { //

第⼆次发现错乱 min = root; cout << max -> val << "hahah"<val << endl; } pre = root; findRecover(root->right, pre, max, min, isFound); }};关键之处：1. ⾸先知晓要⽤到 中序遍历递增的特点；2. 设置⼀个prev指针记录当前操作节点的前⼀个节点，如果当前节点 ⼩于前⼀个节点，则需要调整并记录【注意：是全局的记录！】3. ⼩技巧：如果遍历过程中只出现了⼀次 次序错误，这说明是这两个相邻接点需要被交换；否则出现了两次 次序错误，那就需要继续记录单个

(TreeNode*) min 并最终在主函数 交换这两个节点。【必】(区别删除)拓展题⽬–剪枝 好好利⽤性质！和递归！⽽不是⼀味删除题⽬：我的题解：class Solution {public: /** * @Description:

⽤性质做 * @param {*} * @return {*} * @notes:

*/ TreeNode* trimBST(TreeNode* root, int low, int high) { if(root == nullptr) return nullptr; //

前序！ 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; } TreeNode* trimBST1(TreeNode* root, int low, int high) { if(root == nullptr) return nullptr; root->left = trimBST(root->left, low, high); //

中序 if(root->val < low) { //

三种情况删除当前节点 return trimBST(root->right, low, high); }else if(root->val > high){ return trimBST(root->left, low, high); } root->right = trimBST(root->right, low, high); return root; }};关键之处：理解并明⽩ 使⽤性质！—— 利⽤⼆叉查找树的⼤⼩关系，我们可以很容易地利⽤递归进⾏树的处理。总结通过这篇⽂章，我们总结出了如下⼏个技巧：1、⼆叉树算法设计的总路线：把当前节点要做的事做好，其它的抛给递归框架–返回值我操⼼——不⽤当前的节点操⼼。2、如果当前节点会对下⾯的⼦节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。2.1 分为上述`BST合法性 ⾮全局引⽤的使⽤` 是从上到下的；属于 **递归框架操⼼**。2.2 分为上述`99题恢复BST` —— 是全局引⽤不随递归改变；**也属于我操⼼**。3、在⼆叉树递归框架之上，扩展出⼀套 BST 代码框架：void BST(TreeNode root, int target) { if ( == target) //

找到⽬标，做点什么 if ( < target)

BST(, target); if ( > target) BST(, target);}4、学会了——构建、改查、增、删。【即：合法性、搜索、插⼊、删除。】