当前位置: 首页 > news >正文

代码随想录刷题有感

目录

    • leetcode刷题是可以debug的
    • 关于栈递归跟踪两个变量的方法
      • 并行两个栈实现跟踪:
      • 一个栈同时跟踪两个变量
    • 判断二叉树空节点能不能进入递归
    • 有关递归函数返回值类型的思考

注:这篇文章和cpp语言相关那篇文章相辅相成

leetcode刷题是可以debug的

就是利用cout书写日志,是可以实现运行代码时候进行输出的。
例如,这里对106.从中序与后序遍历序列构造二叉树这道题的讲解就用到了日志进行debug,实际运行代码也会对其中的cout部分内容进行输出。
下图为代码中的日志部分局部内容:
在这里插入图片描述
下图是利用测试案例运行代码时候的输出内容
在这里插入图片描述

关于栈递归跟踪两个变量的方法

并行两个栈实现跟踪:

例如:257. 二叉树的所有路径中的迭代方法。如下图所示:
在这里插入图片描述
这里除了模拟递归需要一个栈,同时还需要一个栈来存放对应的遍历路径。

一个栈同时跟踪两个变量

例如:112. 路径总和
栈里一个元素不仅要记录该节点指针,还要记录从头结点到该节点的路径数值总和。

c++就我们用pair结构来存放这个栈里的元素。
定义为:pair<TreeNode*, int> pair<节点指针,路径数值>
在这里插入图片描述

判断二叉树空节点能不能进入递归

例如:654.最大二叉树中两个版本的代码
在这里插入图片描述
因为第一版的递归终止条件是遇到叶子节点就终止,因此对于空节点就不能进入递归中,需要加入额外判断将空节点排除。(否则递归函数没有对空节点的处理方法则容易出错)
版本二因为终止条件是针对空节点的,因此需要遇到空节点的迭代函数才能终止。

有关递归函数返回值类型的思考

对比101. 对称二叉树简称题1和112. 路径总和简称题2引发的思考。

本节内容主要是对下图所示画横线部分展开了思考:
在这里插入图片描述

题1这道题正常分析是如果发现了不合适的节点就不在遍历下去而是直接不断回溯到根节点,但如下图所示给的正常的递归解法,就算发现了不对称的节点仍要遍历完全部节点才能返回根节点。
在这里插入图片描述
对上图代码进行局部修改,如下图所示,则会发现不对称的节点,直接快速回溯到根节点,而不再进行判断。
在这里插入图片描述
题2给的解法如下图所示,这就实现了“发现合适路径立刻回溯不在进行全部遍历”的功能
在这里插入图片描述
上述两种能够立刻回溯的方法,都是利用到了递归函数的返回值来进行实现的,因此当判断有无,符合不符合的递归函数书写时,要考虑函数的返回值,尤其是返回bool变量。
补充:
98.验证二叉搜索树中的递归解法可以修改为下图所示:
在这里插入图片描述


http://www.mrgr.cn/news/94559.html

相关文章:

  • SpringMVC (二)请求处理
  • Go语言对于MySQL的基本操作
  • 【后端开发面试题】每日 3 题(十三)
  • 图解AUTOSAR_CP_BSW_General
  • Python软件和搭建运行环境
  • [多线程]基于单例懒汉模式的线程池的实现
  • Centos7使用docker搭建redis集群
  • Java 大视界 -- Java 大数据中的异常检测算法在工业物联网中的应用与优化(133)
  • Linux 命令学习记录
  • C++基础 [三] - 面向对象三
  • Java 大视界 -- Java 大数据在智能金融资产定价与风险管理中的应用(134)
  • Keil5下载教程及安装教程(附安装包)
  • Java基础语法练习42(基本绘图-基本的事件处理机制-小坦克的绘制-键盘控制坦克移动)
  • 推荐系统基础
  • 操作系统-八股
  • 每日一题---dd爱框框(Java中输入数据过多)
  • 每日一题---腐烂的苹果(广度优先搜索)
  • 网络爬虫【简介】
  • C++中string常用方法总结
  • 6.PE文件新增节