代码随想录刷题有感

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

leetcode刷题是可以debug的

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

下图是利用测试案例运行代码时候的输出内容

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

并行两个栈实现跟踪：

例如：257. 二叉树的所有路径中的迭代方法。如下图所示：

这里除了模拟递归需要一个栈，同时还需要一个栈来存放对应的遍历路径。

一个栈同时跟踪两个变量

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

c++就我们用pair结构来存放这个栈里的元素。
定义为：pair<TreeNode*, int> pair<节点指针，路径数值>

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

例如：654.最大二叉树中两个版本的代码

因为第一版的递归终止条件是遇到叶子节点就终止，因此对于空节点就不能进入递归中，需要加入额外判断将空节点排除。（否则递归函数没有对空节点的处理方法则容易出错）
版本二因为终止条件是针对空节点的，因此需要遇到空节点的迭代函数才能终止。

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

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

本节内容主要是对下图所示画横线部分展开了思考：

题1这道题正常分析是如果发现了不合适的节点就不在遍历下去而是直接不断回溯到根节点，但如下图所示给的正常的递归解法，就算发现了不对称的节点仍要遍历完全部节点才能返回根节点。

对上图代码进行局部修改，如下图所示，则会发现不对称的节点，直接快速回溯到根节点，而不再进行判断。

题2给的解法如下图所示，这就实现了“发现合适路径立刻回溯不在进行全部遍历”的功能

上述两种能够立刻回溯的方法，都是利用到了递归函数的返回值来进行实现的，因此当判断有无，符合不符合的递归函数书写时，要考虑函数的返回值，尤其是返回bool变量。
补充：
98.验证二叉搜索树中的递归解法可以修改为下图所示：