235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插入操作 ,450.删除二叉搜索树中的节点

简介: 本文介绍了三道与二叉搜索树(BST)相关的经典算法题及其解决方案。第一题是寻找两个节点的最近公共祖先,利用BST的有序性,通过比较节点值来决定遍历方向,从而高效找到目标节点。第二题涉及在BST中插入新节点,根据BST性质递归地找到合适位置完成插入操作。第三题则是删除BST中的指定节点,需考虑五种不同情况以确保树结构和性质不变。这些题目不仅巩固了对二叉搜索树的理解,还锻炼了递归和指针操作的能力,是掌握树结构算法的重要练习。

题目:235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

输出: 6  

解释: 节点  

2  

和节点  

8  

的最近公共祖先是  

6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

输出: 2

解释: 节点  

2

和节点  

4

的最近公共祖先是  

2

, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。

p、q 为不同节点且均存在于给定的二叉搜索树中。

思考历程与知识点:  

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

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

在遍历二叉搜索树的时候就是寻找区间[p->val, q->val](注意这里是左闭又闭)

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

题解:

private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if (cur == NULL) return cur;
                                                        // 中
        if (cur->val > p->val && cur->val > q->val) {   // 左
            TreeNode* left = traversal(cur->left, p, q);
            if (left != NULL) {
                return left;
            }
        }
 
        if (cur->val < p->val && cur->val < q->val) {   // 右
            TreeNode* right = traversal(cur->right, p, q);
            if (right != NULL) {
                return right;
            }
        }
        return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
};

 题目:701. 二叉搜索树中的插入操作

给定二叉搜索树(BST)的根节点 root 和要插入树中的值 value ,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ,新值和原始二叉搜索树中的任意节点值都不同。

注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1:

输入:root = [4,2,7,1,3], val = 5

输出:[4,2,7,1,3,5]

解释:另一个满足题目要求可以通过的树是:

示例 2:

输入:root = [40,20,60,10,30,50,70], val = 25

输出:[40,20,60,10,30,50,70,null,null,25]

示例 3:

输入:root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

输出:[4,2,7,1,3,5]

提示:

树中的节点数将在 [0, 104]的范围内。

-108 <= Node.val <= 108

所有值 Node.val 是 独一无二 的。

-108 <= val <= 108

保证 val 在原始BST中不存在。

题解:

class Solution {
private:
    TreeNode* parent;
    void traversal(TreeNode* cur, int val) {
        if (cur == NULL) {
            TreeNode* node = new TreeNode(val);
            if (val > parent->val) parent->right = node;
            else parent->left = node;
            return;
        }
        parent = cur;
        if (cur->val > val) traversal(cur->left, val);
        if (cur->val < val) traversal(cur->right, val);
        return;
    }
 
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        parent = new TreeNode(0);
        if (root == NULL) {
            root = new TreeNode(val);
        }
        traversal(root, val);
        return root;
    }
};

 题目:450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

首先找到需要删除的节点;

如果找到了,删除它。

示例 1:

输入:root = [5,3,6,2,4,null,7], key = 3

输出:[5,4,6,2,null,null,7]

解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0

输出: [5,3,6,2,4,null,7]

解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0

输出: []

提示:

节点数的范围 [0, 104].

-105 <= Node.val <= 105

节点值唯一

root 是合法的二叉搜索树

-105 <= key <= 105

思考历程与知识点:  

这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况:

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

找到删除的节点

第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点

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

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

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

题解:

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况:没找到删除的节点,遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况:其左孩子为空,右孩子不为空,删除节点,右孩子补位 ,返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况:其右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况:左右孩子节点都不为空,则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            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的右孩子作为新root
                delete tmp;             // 释放节点内存(这里不写也可以,但C++最好手动释放一下吧)
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};


相关文章
|
云计算 运维 存储
aPaaS平台是什么?aPaaS与PaaS有什么区别?
aPaaS和PaaS都可以完成软件的开发和部署,都支持云端访问,而两者的差异主要体现在用户人群和使用环境不一样。
aPaaS平台是什么?aPaaS与PaaS有什么区别?
|
网络协议 网络架构
TCP/IP协议中分包与重组原理介绍、分片偏移量的计算方法、IPv4报文格式
本文章讲述了什么是IP分片、为什么要进行IP分片、以及IP分片的原理及分析。分片的偏移量的计算方法,一个IPv4包前三个分片的示例。还讲述了IPv4表示字段的作用,标志位在IP首部中的格式以及各个标志的意义:.........
5808 0
TCP/IP协议中分包与重组原理介绍、分片偏移量的计算方法、IPv4报文格式
|
机器学习/深度学习 PyTorch TensorFlow
Pytorch学习笔记(二):nn.Conv2d()函数详解
这篇文章是关于PyTorch中nn.Conv2d函数的详解,包括其函数语法、参数解释、具体代码示例以及与其他维度卷积函数的区别。
4349 0
Pytorch学习笔记(二):nn.Conv2d()函数详解
|
存储 缓存 资源调度
# Qwen3-8B 的 TTFT 性能分析:16K 与 32K 输入 Prompt 的推算公式与底层原理详解
Qwen3-8B 是通义实验室推出的 80 亿参数大模型,支持最长 32,768 token 上下文,适用于长文本处理场景。通过 FP8 量化、CUDA Kernel 优化及 RoPE 位置编码技术,提升推理效率与稳定性。模型在 16K 输入下 TTFT 约 150-200ms,32K 输入下约 250-300ms,适用于文档摘要与长对话交互。
3595 8
|
内存技术
Synaptics旗下主流WIFI方案选型参考
WIFI行业经过最近十来年的飞速发展,已经显得含金量不高,遍地都是,但是稳定性是检验WIFI品质的唯一标准,潮起潮落,时间会告诉你最终谁是最可靠! WIFI方案方案选型最主要考虑以下三点:WIFI/BT通信标准、通信接口、吞吐量!接下来析下Synaptics旗下对应的方案! 从WIFI/BT通信标准来看: Wi-Fi 6E有:SYN43756E、SYN43711、SYN4382S、SYN4383; Wi-Fi 6有:SYN43752; Wi-Fi 5有:SYN43598、SYN43456; Wi-Fi 4有:SYN43436、SYN43012、BCM430132;
1300 6
|
数据采集 数据可视化 数据挖掘
如何进行有效的数据清洗?
如何进行有效的数据清洗?
1648 3
|
机器学习/深度学习 自然语言处理 监控
利用机器学习进行情感分析:技术详解与实践
【5月更文挑战第13天】本文探讨了利用机器学习进行情感分析的方法,包括技术原理、常用算法和实践应用。情感分析涉及文本预处理(如清洗、分词和去除停用词)、特征提取(如词袋模型、TF-IDF和Word2Vec)及分类器训练(如朴素贝叶斯、SVM和RNN/LSTM)。常见情感分析算法有朴素贝叶斯、支持向量机和深度学习模型。实践中,情感分析应用于社交媒体监控、产品评论分析等领域。通过本文,读者可了解情感分析的基础知识及其应用价值。
1945 2
|
运维 JavaScript Linux
容器内的Nodejs应用如何获取宿主机的基础信息-系统、内存、cpu、启动时间,以及一个df -h的坑
本文介绍了如何在Docker容器内的Node.js应用中获取宿主机的基础信息,包括系统信息、内存使用情况、磁盘空间和启动时间等。核心思路是将宿主机的根目录挂载到容器,但需注意权限和安全问题。文章还提到了使用`df -P`替代`df -h`以获得一致性输出,避免解析错误。
1080 1
|
Docker Windows 容器
clash代理docker实现镜像拉取
clash代理docker实现镜像拉取
7706 1