代码随想录刷题笔记2

news/2024/4/24 20:01:12/

文章目录

  • 二叉树
    • 递归遍历
    • 统一迭代形式
    • 层序遍历
      • 迭代形式——队列
    • 题型
      • 删除普通二叉树目标节点
      • 两棵树比较
    • 递归模板
      • 深度、高度问题
      • 完全二叉树
        • 判断完全二叉树
      • 平衡二叉树
      • 左叶子
      • 最大树
      • 二叉搜索树
      • 最近公共祖先

二叉树

递归遍历

  • 递归三部曲
    • 确定递归函数的 参数 与 返回值。
    • 确定终止条件。
    • 确定单层递归逻辑。
  • 前中后序遍历
  • 实现细节
    • C++语言实现时,传入vector作为存放结果容器,但是递归函数的参数忘记写成引用形式,导致都是拷贝形式传参。
    • 注意:可能是上述前中后3中遍历模板题目,但不是常规意义上的,如可能找右中左这样的中序遍历顺序
    • 代码
      void traversal(TreeNode* root, vector<int>& ans)
      

统一迭代形式

使用栈的话,无法同时解决访问节点(遍历节点)和处理节点(将元素放进结果集)不一致的情况。
故将访问的节点放入栈中,把要处理的节点也放入栈中但是要做标记。

即 将要处理的节点放入栈之后,紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

  • 注意点
    由于 结合了栈,代码逻辑 和 具体遍历顺序相反。
  • 前序模板
	vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;if (!root)return ans;stack<TreeNode*> stk;stk.push(root);while (!stk.empty()) {TreeNode* p = stk.top();if (p != nullptr) {stk.pop();if (p->right)stk.push(p->right);if (p->left)stk.push(p->left);stk.push(p);stk.push(nullptr);}else {stk.pop();p = stk.top();stk.pop();ans.push_back(p->val);}}return ans;}
  • 中序模板
    vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;if (root == nullptr)return ans;stack<TreeNode*> stk;stk.push(root);while (!stk.empty()) {TreeNode* p = stk.top();//访问节点if (p != nullptr) {stk.pop();if (p->right)stk.push(p->right);stk.push(p);//添加标记stk.push(nullptr);if (p->left)stk.push(p->left);}else {//处理节点stk.pop();p = stk.top();stk.pop();ans.push_back(p->val);}}return ans;}

层序遍历

迭代形式——队列

  • 模板
        vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;if (root == nullptr)return ans;queue<TreeNode*> que;que.push(root);while (!que.empty()) {int size = que.size();vector<int> level;while (size > 0) {size--;TreeNode* p = que.front();que.pop();level.push_back(p->val);if (p->left != nullptr)que.push(p->left);if (p->right != nullptr)que.push(p->right);}ans.push_back(level);}return ans;}
    
  • 层间操作

题型

删除普通二叉树目标节点

要遍历整棵树。
与下文中二叉搜索树的删除节点类似,调整结构,对目标节点分类。

  • 代码(随想录)
    • 交换值的操作来删除目标节点
      思想:将目标节点值 和 右子树的最左节点值交换,之后目标节点变为了该最左节点,这是第一次;继续递归遍历,一直遍历到该最左节点即目标节点,然后若是右孩子为空,直接返回左孩子,这是第二次操作目标节点,注意若是右孩子不空,则会继续交换,然后重复,直到右孩子为空,可以删除。
        TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root;if (root->val == key) {if (root->right == nullptr) { // 这里第二次操作目标值:最终删除的作用return root->left;}TreeNode *cur = root->right;while (cur->left) {cur = cur->left;}swap(root->val, cur->val); // 这里第一次操作目标值:交换目标值其右子树最左面节点。}root->left = deleteNode(root->left, key);root->right = deleteNode(root->right, key);return root;}
    
    • 参考二叉搜索树,用指针 断开、重连等直接操作。

两棵树比较

  • 二叉树自身子树比较——对称性质
    • 要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否对应相等。
      • 即一个树的遍历顺序是左右中,一个树的遍历顺序是右左中,二者同步进行遍历。
      • 都可理解为是后序遍历,尽管已经不是严格上在一个树上进行遍历的后序遍历。
    • 递归模板

      class Solution {
      public:bool isSymmetric(TreeNode* root) {if (!root)return true;return traversal(root->left, root->right);}bool traversal(TreeNode* r1, TreeNode* r2) {if (!r1 && !r2)return true;if ((!r1 && r2) || (r1 && !r2) || (r1->val != r2->val))return false;bool outside = traversal(r1->left, r2->right);bool inside = traversal(r1->right, r2->left);return outside && inside;}
      };
      
    • 迭代
      • 任意使用 队列、栈、数组等容器,依然是 子树1的内侧节点和子树2的内侧节点同时进入容器,相应外侧节点同时进入。
  • 比较两棵树是否相同
    • 类似 对称性质比较,只是 是 两棵树的 左节点 同时进入 、两棵树的右节点同时进入。
  • 两棵树同时操作
    • 递归
    • 迭代法中,一般一起操作两个树都是使用队列模拟类似层序遍历,同时处理两个树的节点,这种方式最好理解,如果用模拟递归的思路的话,要复杂一些。

深度、高度问题

  • 定义
    • 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
    • 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数后者节点数(取决于高度从0开始还是从1开始)
  • 角度转移
    • 当前节点的高度:以当前节点为根节点求最大深度,可以用后序遍历。
  • 方法
    • 递归
      • 前序遍历:求根节点高度。
      • 后序遍历:求当前节点深度。
    • 迭代
      • 层序遍历:适合求当前节点的深度。
  • 代码模板
    // 递归-后序遍历:求最小深度int traversal(TreeNode* root) {if (!root)return 0;int leftDpeth = traversal(root->left);int rightDpeth = traversal(root->right);if (root->left && !root->right)return 1 + leftDpeth;if (!root->left && root->right)return 1 + rightDpeth;return 1 + min(leftDpeth, rightDpeth);}// 递归-后序遍历:求最大深度int getdepth(treenode* node) {if (node == NULL) return 0;int leftdepth = getdepth(node->left);       // 左int rightdepth = getdepth(node->right);     // 右int depth = 1 + max(leftdepth, rightdepth); // 中return depth;}

完全二叉树

判断完全二叉树

  • DFS
    后序遍历,一直向左递归的深度 == 一直向右递归的深度
        TreeNode* left = root->left, * right = root->right;int leftDepth = 0, rightDepth = 0;while (left) {left = left->left;leftDepth++;}while (right) {right = right->right;rightDepth++;}if (leftDepth == rightDepth)return (2 << leftDepth) - 1;// 注意(2<<1) 相当于2^2,所以leftDepth初始为0
  • BFS
    层序遍历,结合 层数 和 当前层节点 之间的次幂关系。
        while (!que.empty()) {level++;int levelSize = que.size();ans += levelSize;int levelMaxSize = int(pow(2, level - 1));if (levelSize != levelMaxSize) {ans = levelMaxSize - 1 + levelSize;break;}

平衡二叉树

  • 概念
    任意节点的左右子树的高度差值 不超过1.

  • 深度 和 高度

    • 深度:指从根节点到该节点的最长简单路径边的条数。
    • 高度:指从该节点到叶子节点的最长简单路径边的条数。
  • 代码

    • 递归——后序遍历(比较高度)
      • 参数,返回值
        • 返回值:0表示当前节点的左右子树高度相等;-1表示当前节点的左右子树已经违反平衡二叉树的规则,直接中断判断;x表示当前节点的高度。
      • 代码
      int getHeight(TreeNode* root) {int leftHeight = getHeight(node->left); // 左if (leftHeight == -1) return -1;int rightHeight = getHeight(node->right); // 右if (rightHeight == -1) return -1;int result;if (abs(leftHeight - rightHeight) > 1) {  // 中result = -1;} else {result = 1 + max(leftHeight, rightHeight); // 以当前节点为根节点的树的最大高度}return result;
      }
      
    • 迭代——后序遍历的迭代形式
      • 以当前节点为根节点,求其子树的最大深度 即该节点的高度。

左叶子

  • 当前节点的左孩子是否为叶子。
  • 反常规,通过父节点判断 左孩子,而非常规通过孩子判断父节点。

最大树

  • 类似用数组构造二叉树的题目,每次分隔尽量不要定义新的数组,而是通过下标索引直接在原数组上操作,这样可以节约时间和空间上的开销。
    • 在递归时可用 索引限制每次递归处理的范围,如[begin, end)
  • 不同代码风格的实现,一般情况来说:如果让空节点(空指针)进入递归,就不加if,如果不让空节点进入递归,就加if限制一下, 终止条件也会相应的调整。
    • 允许空节点进入,则会代码简洁一些。

二叉搜索树

  • 关键点
    中序遍历

  • 一种常见手法
    中序遍历时的pre指针

  • 节点有序

    • 在二叉树上进行二分查找。
  • 查找

    • 递归
      • 由于节点有序性,不需要回溯。
  • 验证二叉搜索树

    • 借助中序遍历,使用一个pre指针,次一点则是借助数组存储中序结果。
    • 代码
        // 下列 pre指针是 引用类型bool traversal(TreeNode* root, TreeNode* & pre) {if (!root)return true;bool left = traversal(root->left, pre);if (pre && pre->val >= root->val)return false;            pre = root;bool right = traversal(root->right, pre);return left && right;}
    
  • 二叉搜索树插入节点
    正常遍历,然后插入在叶子节点即可,无需涉及结构调整。

  • 二叉搜索树删除节点
    需要涉及到 结构调整。

    • 递归函数返回值问题
      因为涉及到结构调整,所以下层操作完后,回溯后,需要更新结构,对父节点的孩子节点重新设置。
      相当于把新的节点返回给上一层,上一层就要用 root->left 或者 root->right接住。
    • 目标节点 进行分类:
      • 目标节点为叶子节点,直接删除。
      • 目标节点有一边为空,则用非空的孩子顶替 目标节点位置。
      • 目标节点同时有左右孩子,将左孩子放在右孩子树的最左节点的左孩子位置。
    • 代码(随想录)
      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的右孩子作为新rootdelete 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;
      }
      

最近公共祖先

  • 需求
    自底向上搜索,查看公共祖先,故用到回溯过程,即 后序遍历。
  • 回溯过程中的返回值问题
    • 在回溯的过程中,必然要遍历整棵二叉树[重点],即使已经找到结果了,依然要把其他节点遍历完,因为要使用递归函数的返回值(也就是代码中的left和right)做逻辑判断。

    • 要理解如果返回值left为空,right不为空为什么要返回right,为什么可以用返回right传给上一层结果。

    • 本题就是标准的搜索整棵树的写法,遇到递归函数的返回值,需要对返回值进行处理,模板如下:

      • 搜索一条边
    if (递归函数(root->left)) return ;
    if (递归函数(root->right)) return ;
    
    • 搜索整棵树
    left = 递归函数(root->left);
    right = 递归函数(root->right);
    left与right的逻辑处理;
    
    • 返回值,一般也可以建立父节点和子节点之间的关系。

http://www.ppmy.cn/news/48096.html

相关文章

【Vue全家桶】Pinia状态管理

【Vue全家桶】Pinia状态管理 文章目录 【Vue全家桶】Pinia状态管理写在前面一、认识Pinia1.1 认识Pinia1.2 为什么使用Pinia&#xff1f; 二、 Store2.1 定义Store2.2 Option对象2.3 setup函数2.4 使用定义的Store 三、Pinia核心概念State3.1 定义State3.2 操作State3.3 使用选…

为何MySQL 8.0开始取消了查询缓存

官方文档说明&#xff1a;MySQL :: MySQL 8.0: Retiring Support for the Query Cache MySQL查询缓存是查询结果缓存。它将以SEL开头的查询与哈希表进行比较&#xff0c;如果匹配&#xff0c;则返回上一次查询的结果。 进行匹配时&#xff0c;查询必须逐字节匹配&#xff0c;例…

Android:usb转232串口通信

准备工作 首先得adb进入盒子root模式&#xff0c;将/dev/ttys1这个文件改为777&#xff0c;使得所有用户可操作 adb root adb remount adb shell 进入设备的root模式&#xff0c;执行 chmod 777 /dev/ttys1 执行完成后退出 exit 再执行 adb shell chmod 666 /dev/ttyS1 如…

比较运算符、关键字子查询MySQL数据库 (头歌实践教学平台)

文章目的初衷是希望学习笔记分享给更多的伙伴&#xff0c;并无盈利目的&#xff0c;尊重版权&#xff0c;如有侵犯&#xff0c;请官方工作人员联系博主谢谢。 目录 第1关&#xff1a;带比较运算符的子查询 任务描述 相关知识 子查询 带比较运算符的子查询 编程要求 第2关…

第二章 法的内容与形式

目录 第一节 法的内容与形式的概念 一、法的内容与形式的含义 二、法的内容和形式的关系 第二节 法律权利与法律义务 一、权利和义务的概念 二、权利和义务的分类 三、权利与义务的联系 第三节 法的成文形式与不成文形式 一、历史上各种法的表现形式 二、成文法与不成文…

Vue中组件传值

Vue官网链接-向子组件传递数据 Vue官网-Prop 父组件将值传递给子组件 父组件中的值可以通过v-bind与子组件中的props属性将值传递给子组件&#xff0c;也可以通过v-on与this.$emit()间接被子组件中的函数调用 1、使用v-bind将父组件中data中的键与子组件中的props键进行绑定 …

【SpringBoot】一:SpringBoot的基础(下)

文章目录 1.外部化的配置1.1 配置文件基础1.1.1 配置文件格式1.1.2 application文件1.1.3 application.properties1.1.4 application.yml1.1.5 environment1.1.6 组织多文件1.1.7多环境配置 1.2 绑定Bean1.2.1 简单的属性绑定1.2.2 嵌套Bean1.2.3 扫描注解1.2.4 处理第三方库对…

Vue中mixins(混入)的介绍和使用

什么是Mixin&#xff1f; 想要使用一个事物或者工具&#xff0c;我们首要先了解它是什么&#xff0c;这样我们才好对症下药。 其实Mixin不是Vue专属的&#xff0c;可以说它是一种思想&#xff0c;也可以说它就是混入的意思&#xff0c;在很多开发框架中都实现了Mixin(混入)&a…

异常(throwable)

异常 异常分类 &#xff08;1&#xff09;Throwable类 所有的异常类型都是它的子类&#xff0c;它派生两个子类Error、Exception。 &#xff08;2&#xff09;Error类 表示仅靠程序本身无法恢复的严重错误&#xff08;内存溢出动态链接失败、虚拟机错误&#xff09;&#…

Seata强一致性事务模式XA的设计理念

承接上文分布式事务Seata-AT模式 XA规范是什么? 是分布式事务处理DTP&#xff08;Distributed Transaction Processing&#xff09;的标准。是描述全局的事务管理器和局部的资源管理器之间的接口规范。允许多个资源&#xff08;如数据库、应用服务、消息队列&#xff09;在同…

class与typename的异同

一、class与typename的相同点 typename关键字常用于函数模板&#xff0c;这里首先引入函数模板的概念&#xff1a;函数模板代表了一个函数家族&#xff0c;该函数模板与类型无关&#xff0c;在使用时被参数化&#xff0c;根据实参类型产生函数的特定 类型版本 //函数模板格式…

idea 配置docker 进行上传镜像,部署启动容器

前言 在我们开发测试过程中&#xff0c;需要频繁的更新docker镜像&#xff0c;然而默认情况下&#xff0c;docker的2375端口是关闭的&#xff0c;下面介绍如何打开端口。 修改docker配置文件 操作步骤&#xff1a; 1.1、修改配置 登录docker所在服务器&#xff0c;修改docker…

深入浅出剖析JAVA多线程原理

1. 线程基础知识 1.1 线程与进程 1.1.1 进程 ●程序由指令和数据组成&#xff0c;但这些指令要运行&#xff0c;数据要读写&#xff0c;就必须将指令加载至 CPU&#xff0c;数据加载至内存。在指令运行过程中还需要用到磁盘、网络等设备。进程就是用来加载指令、管理内存、管理…

聚观早报|马斯克将TruthGPT挑战ChatGPT;腾讯披露自研芯片新进展

今日要闻&#xff1a;马斯克将TruthGPT挑战ChatGPT&#xff1b;苹果在印度年销售额近60亿美元&#xff1b;腾讯披露自研芯片沧海最新进展&#xff1b;特斯拉中国工厂普通工人月薪约1万元&#xff1b;飞猪将直接向阿里CEO张勇汇报 马斯克将TruthGPT挑战ChatGPT 4 月 18 日消息&…

【大厂直通车】哔哩哔哩日常实习_测开面经

📑哈喽,大家好,我是小浪;本篇博客更新的是最新B站测开面经,本专栏非常适合目前准备找实习,或者准备冲秋招测试,测开方向的同学阅读订阅,持续更新各大厂真题面经,带你成为offer收割机!! 🧃对于订阅本专栏的同学们,博主在努力更新,只需要一杯奶茶钱,订阅本专栏,…

数据结构(三)—— 哈希表

文章目录 一、哈希表积累1.1 哈希map1.2 哈希set 二、哈希表基础三、题3.1 242 有效的字母异位词3.2 349 两个数组的交集3.3 202 快乐数3.4 1 两数之和3.5 54 四数相加II 一、哈希表积累 什么时候想到用哈希法&#xff1a;当要需要查询一个元素是否出现过、判断一个元素是否出…

从单兵作战到生态共创,纵目科技打响智驾2.0新战役

4月18日&#xff0c;第十二届上海国际汽车工业展览会&#xff08;简称&#xff1a;2023上海车展&#xff09;在上海国家会展中心盛大启幕。纵目科技携最新自动驾驶解决方案——Amphiman 3000、8000行泊一体解决方案、Trinity 3000、8000舱行泊一体解决方案以及众多摄像头产品强…

C++智能指针unique_ptr

智能指针的设计思路 智能指针是类模板&#xff0c;在栈上创建智能指针对象。把普通指针交给智能指针对象。当智能指针对象过期时&#xff0c;调用析构函数释放普通指针的内存。 有unique_ptr,shared_ptr和weak_ptg三种智能指针 unique_ptr unique_ptr独享它指向的对象&…

深度学习笔记之残差网络(ResNet)

深度学习笔记之残差网络[ResNet] 引言引子&#xff1a;深度神经网络的性能问题核心问题&#xff1a;深层神经网络训练难残差网络的执行过程残差网络结构为什么能够解决核心问题残差网络的其他优秀性质 引言 本节将介绍残差网络( Residual Network,ResNet \text{Residual Netwo…

【nacos配置中心】源码部分解析

启动初始化 SpringApplication.prepareContext applyInitializers 回调ApplicationContextInitializer的initialize方法 getInitializers()从applicationContext获取List<ApplicationContextInitializer<?>> initializers 这个集合是通过SpringApplication的…