代码随想录 10.13 || 二叉树 LeetCode 235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

news/2024/4/17 17:03:43

二叉树的定义:

        回顾一下二叉树的定义,加固记忆。

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptre) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

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

        与普通二叉树中的最近公共祖先不同,求二叉搜索树的最近公共祖先更为容易一些,因为二叉搜索树自带顺序性,我们可以根据节点的值寻找目标节点的位置。

        如果,当前节点的值同时大于 节点 p 和 q 的值,说明 p 和 q 在当前节点的左子树中,反之则位于右子树中。

        如果,当前节点的值大于其中一个节点,小于另一个节点,当前节点即为给定节点 p 和 q 的最近公共祖先。

class Solution { // 递归法
private:TreeNode* traversal(TreeNode *node, TreeNode *p, TreeNode *q) {if (node->val > p->val && node->val > q->val) return traversal(node->left, p, q);if (node->val < p->val && node->val < q->val) return traversal(node->right, p, q);return node;}public:TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {if (root == nullptr) return root;return traversal(root, p, q);}
};

        在递归法中,我们递归遍历二叉树,在不满同时大于或小于条件时,直接返回当前节点,即最近公共祖先。

class Solution { // 迭代法
public:TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {while(root) {if (root->val > p->val && root->val > q->val) root = root->left;else if (root->val < p->val && root->val < q->val) root = root->right;else return root;}return nullptr;}
};

        迭代法代码则更为简洁,使用 while 一直向下遍历,直至找到目标节点为止,如果未找到,则说明目标不存在给定二叉树中。

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

        向一颗二叉搜索树中插入一个节点,众所周知,在二叉搜索树中,左子树的值一定小于根节点的值,右子树的值一定大于根节点的值,我们需要找到合适的位置插入给定节点,而不是应该随意插入,插入完成后的树,应该保持二叉搜索树的性质。

class Solution { // 递归法
private:TreeNode* traversal(TreeNode *node, int val) {if (node->val > val && node->left != nullptr) return traversal(node->left, val);if (node->val < val && node->right != nullptr) return traversal(node->right, val);return node;}public:TreeNode* insertIntoBST(TreeNode *root, int val) {if (root == nullptr) {TreeNode *node = new TreeNode(val);return node;}TreeNode *fnode = traversal(root, val);TreeNode *cnode = new TreeNode(val);if (fnode->val > val) fnode->left = cnode;else fnode->right = cnode;return root;}
};

        在递归法中,我们仍然利用二叉搜索树的性质,寻找插入位置。如果,待插入节点的值小于当前节点,且当前节点的左子树不为空,则向左子树遍历;如果,待插入节点的值大于当前节点,且当前节点的右子树不为空,则向右子树遍历。不满足上述条件,则说明当前节点的左子树或右子树为空,此时我们就找到了插入位置的父节点,将其返回。在主函数中,我们定义一个 fnode 接收返回节点,然后以 val 初始化一个节点,并根据 val 的值,将其添加到 fnode 的左子树或右子树上。在最后,返回更新过后的 root 即可。

class Solution { // 迭代法
public:TreeNode* insertIntoBST(TreeNode *root, int val) {if (root == nullptr) {TreeNode *node = new TreeNode(val);return node;}TreeNode *cur = root;while(1) {if (cur->val > val && cur->left != nullptr) cur = cur->left;else if (cur->val < val && cur->right != nullptr) cur = cur->right;else break;}TreeNode *node = new TreeNode(val);if (cur->val > val) cur->left = node;else cur->right = node;return root;}
};

        迭代法代码更为简洁,同样利用循环找位置,然后添加新节点至目标位置。

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

        与向二叉搜索树中添加节点不同,从树中删除节点会破坏树的结构,涉及到树的重塑。分析,如果删除二叉搜索树中的某一个节点,存在以下四种情况:

        1)待删除节点为叶子节点,不需要更改树的结构,直接将待删除节点置空;

        2)待删除节点的左叶子节点不为空,右叶子节点为空,将待删除节点的左子树上移;

        3)待删除节点的左叶子节点为空,右叶子节点不为空,将待删除节点的右子树上移;

        4)如果待删除节点的左右子树都不为空,需要更改二叉搜索树的结构,以确保删除节点后,仍然保持二叉搜索树的性质。可以将待删除节点的左子树挂到右子树的最左节点下,也可将待删除节点的右子树挂到左子树的最右节点下,在此我们选择第一种方法。

class Solution {
public:TreeNode* deleteNode(TreeNode *root, int key) {if (root == nullptr) return root;if (root->val == key) {if (root->left == nullptr && root->right == nullptr){delete root;return nullptr;} else if (root->left == nullptr && root->right != nullptr) {TreeNode *node = root->right;delete root;return node;} else if (root->left != nullptr && root->right == nullptr) {TreeNode *node = root->left;delete root;return node;} else {TreeNode *node = root->right;while (node->left != nullptr) node = node->left;node->left = root->left;TreeNode *tmp = root;root = root->right;delete tmp;return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;}
};

        在最后返回根节点 root,如果删除发生在左子树,则用左子树接收变更后的左子树,右子树亦然。


https://www.xjx100.cn/news/3092580.html

相关文章

Redis从入门到精通(三)-高阶篇

文章目录 0. 前言[【高阶篇】3.1 Redis协议(RESP )详解](https://blog.csdn.net/wangshuai6707/article/details/132742584)[【高阶篇】3.3 Redis之底层数据结构简单动态字符串(SDS)详解](https://blog.csdn.net/wangshuai6707/article/details/131101404)[【高阶篇】3.4 Redis…

手把手带你在AutoDL上部署InternLM-Chat-7B Transformers

手把手带你在AutoDL上部署InternLM-Chat-7B Transformers 调用 项目地址&#xff1a;https://github.com/KMnO4-zx/self_llm.git 如果大家有其他模型想要部署教程&#xff0c;可以来仓库提交issue哦~ 也可以自己提交PR&#xff01; InternLM-Chat-7B Transformers 部署调用 环…

使用pytorch利用神经网络原理进行图片的训练(持续学习中....)

1.做这件事的目的 语言只是工具,使用python训练图片数据,最终会得到.pth的训练文件,java有使用这个文件进行图片识别的工具,顺便整合,我觉得Neo4J正确率太低了,草莓都能识别成为苹果,而且速度慢,不能持续识别视频帧 2.什么是神经网络?(其实就是数学的排列组合最终得到统计结果…

3D 纹理渲染如何帮助设计师有效、清晰地表达设计理念

在线工具推荐&#xff1a; 三维数字孪生场景工具 - GLTF/GLB在线编辑器 - Three.js AI自动纹理化开发 - YOLO 虚幻合成数据生成器 - 3D模型在线转换 - 3D模型预览图生成服务 定义 3D 渲染可视化及其用途 3D 可视化是一种艺术形式。这是一个机会。这是进步。借助 3D 纹理…

Linux中的MFS分布式文件系统

目录 一、MFS分布式文件系统 1、MooseFS简介 2、Moose File System的体系结构 &#xff08;1&#xff09;MooseFS Master &#xff08;2&#xff09;MooseFS Chunk Server &#xff08;3&#xff09;MooseFS Metalogger &#xff08;4&#xff09;MooseFS Client &…

matlab-BP神经网络的训练参数大全

本文部分图文来自《老饼讲解-BP神经网络》bp.bbbdata.com 本文列兴趣MATLAB神经网络工具箱中&#xff0c;训练参数trainParam的各个参数与意义 以方便在使用matlab工具箱时&#xff0c;用于查阅 一、matlab神经网络工具箱trainParam的参数列表 trainParam中的各个具体参数如下…

美团面试:微服务如何拆分?原则是什么?

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50)中&#xff0c;最近有小伙伴拿到了一线互联网企业如美团、字节、如阿里、滴滴、极兔、有赞、希音、百度、网易的面试资格&#xff0c;遇到很多很重要的面试题&#xff1a; 微服务如何拆分&#xff1f; 微服务拆分的规范和原则…

JavaScript-变量类型判断

更多内容&#xff0c;请访问&#xff1a; 声明和定义区别 JavaScript-变量类型 JavaScript-如何使用变量 JavaScript-undefined和null区别 变量类型判断 typeof 常用于基础数据类型判断: typeof 123 number; // true typeof true boolean; // true typeof 123 string…