算法训练day22Leetcode236二叉搜索树的最近祖先701二叉搜索树中的插入操作450删除二叉搜索树中的节点

2024-01-29 09:20
文章标签 算法 训练 操作 搜索 二叉 删除 树中 插入 节点 最近 祖先 450 701 day22leetcode236

本文主要是介绍算法训练day22Leetcode236二叉搜索树的最近祖先701二叉搜索树中的插入操作450删除二叉搜索树中的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目描述

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

我的想法

利用二叉搜索树特性遍历，从上到下遍历

题目分析

在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？

因为是有序树，所有 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。

递归法
递归三部曲如下：

  1. 确定递归函数返回值以及参数
    参数就是当前节点，以及两个结点 p、q。

返回值是要返回最近公共祖先，所以是TreeNode * 。

代码如下：

TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
  1. 确定终止条件
    遇到空返回就可以
if (cur == nullptr) return cur;

其实都不需要这个终止条件，因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。

  1. 确定单层递归逻辑
    在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭又闭）

那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上）。

需要注意的是此时不知道p和q谁大，所以两个都要判断

代码如下：

if (cur->val > p->val && cur->val > q->val) {TreeNode* left = traversal(cur->left, p, q);if (left != NULL) {return left;}
}

如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树。

搜索一条边的写法：
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
搜索整个树写法：left = 递归函数(root->left);
right = 递归函数(root->right);

left与right的逻辑处理;
本题就是标准的搜索一条边的写法，遇到递归函数的返回值，如果不为空，立刻返回。

如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树）。

剩下的情况，就是cur节点在区间（p->val <= cur->val && cur->val <= q->val）或者 （q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。

acm模式代码

#include <iostream>
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) return nullptr;if (root->val > p->val && root->val > q->val) {TreeNode* left = lowestCommonAncestor(root->left, p, q);if (left != nullptr) return left;    }if (root->val < p->val && root->val < q->val) {TreeNode* right = lowestCommonAncestor(root->right, p, q);if (right != nullptr) return right;}return root;}
};int main() {// Example tree creationTreeNode* root = new TreeNode(6);root->left = new TreeNode(2);root->right = new TreeNode(8);root->left->left = new TreeNode(0);root->left->right = new TreeNode(4);root->left->right->left = new TreeNode(3);root->left->right->right = new TreeNode(5);root->right->left = new TreeNode(7);root->right->right = new TreeNode(9);Solution sol;TreeNode* p = root->left; // For example, node with value 2TreeNode* q = root->right; // For example, node with value 8TreeNode* lca = sol.lowestCommonAncestor(root, p, q);if (lca != nullptr) {std::cout << "Lowest Common Ancestor: " << lca->val << std::endl;} else {std::cout << "No common ancestor found." << std::endl;}// Clean up memorydelete root->left->right->right;delete root->left->right->left;delete root->left->right;delete root->left->left;delete root->right->right;delete root->right->left;delete root->left;delete root->right;delete root;return 0;
}

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

题目描述

https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/

我的想法

采用中序遍历

题目分析

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了

递归三部曲：

  1. 确定递归函数参数以及返回值
    参数就是根节点指针，以及要插入元素，这里递归函数要不要有返回值呢？

可以有，也可以没有，但递归函数如果没有返回值的话，实现是比较麻烦的，下面也会给出其具体实现代码。

有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作。（下面会进一步解释）

递归函数的返回类型为节点类型TreeNode * 。

代码如下：

TreeNode* insertIntoBST(TreeNode* root, int val)
  1. 确定终止条件
    终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。

代码如下：

if (root == NULL) {TreeNode* node = new TreeNode(val);return node;
}

这里把添加的节点返回给上一层，就完成了父子节点的赋值操作了，详细再往下看。

  1. 确定单层递归逻辑

    此时要明确，需要遍历整棵树么？

别忘了这是搜索树，遍历整棵搜索树简直是对搜索树的侮辱。

搜索树是有方向了，可以根据插入元素的数值，决定递归方向。

代码如下：

if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;

acm模式代码

#include <iostream>
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) return nullptr;if (root->val > p->val && root->val > q->val) {TreeNode* left = lowestCommonAncestor(root->left, p, q);if (left != nullptr) return left;    }if (root->val < p->val && root->val < q->val) {TreeNode* right = lowestCommonAncestor(root->right, p, q);if (right != nullptr) return right;}return root;}
};int main() {// Example tree creationTreeNode* root = new TreeNode(6);root->left = new TreeNode(2);root->right = new TreeNode(8);root->left->left = new TreeNode(0);root->left->right = new TreeNode(4);root->left->right->left = new TreeNode(3);root->left->right->right = new TreeNode(5);root->right->left = new TreeNode(7);root->right->right = new TreeNode(9);Solution sol;TreeNode* p = root->left; // For example, node with value 2TreeNode* q = root->right; // For example, node with value 8TreeNode* lca = sol.lowestCommonAncestor(root, p, q);if (lca != nullptr) {std::cout << "Lowest Common Ancestor: " << lca->val << std::endl;} else {std::cout << "No common ancestor found." << std::endl;}// Clean up memorydelete root->left->right->right;delete root->left->right->left;delete root->left->right;delete root->left->left;delete root->right->right;delete root->right->left;delete root->left;delete root->right;delete root;return 0;
}

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

题目描述

https://leetcode.cn/problems/delete-node-in-a-bst/description/

题目分析

搜索树的节点删除要比节点增加复杂的多，有很多情况需要考虑

递归
递归三部曲：

  1. 确定递归函数参数以及返回值

说到递归函数的返回值，在二叉树：搜索树中的插入操作 (opens new window)中通过递归返回值来加入新节点， 这里也可以通过递归返回值删除节点。

代码如下：

TreeNode* deleteNode(TreeNode* root, int key)
  1. 确定终止条件

遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了

if (root == nullptr) return root;
  1. 确定单层递归的逻辑
    这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了

找到删除的节点

第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点

第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点

第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点

第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

if (root->val == key) {// 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点// 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点if (root->left == nullptr) return root->right;// 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点else if (root->right == nullptr) return root->left;// 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置// 并返回删除节点右孩子为新的根节点。else {TreeNode* cur = root->right; // 找右子树最左面的节点while(cur->left != nullptr) {cur = cur->left;}cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置TreeNode* tmp = root;   // 把root节点保存一下，下面来删除root = root->right;     // 返回旧root的右孩子作为新rootdelete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）return root;}
}
// 相当于把新的节点返回给上一层，上一层就要用 root->left 或者 root->right接住，代码如下：
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;

acm模式代码

#include <iostream>
struct TreeNode
{int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode* left, TreeNode* right):val(x), left(left), right(right) {}
};class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {//1.确定终止条件if (root == nullptr) {return nullptr;}if (root->val == key) {//左右子树都为空,说明自身是叶子节点if (root->left == nullptr && root->right == nullptr) {return nullptr;}//左子树为空，右子树不为空else if (root->left == nullptr && root->right != nullptr) {return root->right;}//左子树不为空，右子树为空else if (root->left != nullptr && root->right == nullptr) {return root->left;}//左右子树都不为空else {TreeNode* cur = root->right;while (cur->left != nullptr) {cur = cur->left;}cur->left = root->left;return root->right ;}}//2.确定单层递归if (root->val > key) {root->left = deleteNode(root->left, key);}else if (root->val < key) {root->right = deleteNode(root->right, key);}return root;}
};void printInOrder(TreeNode* node) {if (node == nullptr) {return;}printInOrder(node->left);std::cout << node->val << " ";printInOrder(node->right);
}void deleteTree(TreeNode* node) {if (node == nullptr) {return;}deleteTree(node->left);deleteTree(node->right);delete node;
}int main() {// 创建测试树TreeNode* root = new TreeNode(5);root->left = new TreeNode(3);root->right = new TreeNode(6);root->left->left = new TreeNode(2);root->left->right = new TreeNode(4);root->right->right = new TreeNode(7);// 打印原始树std::cout << "原始树的中序遍历: ";printInOrder(root);std::cout << std::endl;// 删除节点Solution solution;root = solution.deleteNode(root, 3); // 例如，删除值为3的节点// 打印更新后的树std::cout << "删除节点后的中序遍历: ";printInOrder(root);std::cout << std::endl;// 清理分配的内存deleteTree(root);
}

今日学习链接

https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E6%80%9D%E8%B7%AF

这篇关于算法训练day22Leetcode236二叉搜索树的最近祖先701二叉搜索树中的插入操作450删除二叉搜索树中的节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/656441。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj1330（LCA最近公共祖先）

poj1330（LCA最近公共祖先）

题意：求最近公共祖先 思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2