算法
这几天努了努力,把代码随想录的二叉树专题全刷完了:
简单按照网站中(二叉树系列)总结一下这几天刷的二叉树内容,然后对二叉树专题进行一个大总结。
合并两个二叉树时,平时我们都习惯了操作一个二叉树,一起操作两个树可能还有点陌生。其实套路是一样,只不过一起操作两个树,递归法还是同样的原理,无非是两个树同时开始比较;
迭代法中,一般一起操作两个树都是使用队列模拟类似层序遍历,同时处理两个树的节点,这种方式最好理解,如果用模拟递归的思路的话,要复杂一些。
涉及到二叉搜索树(Binary Search Tree,BST) ,开始要换一个思路了,大多是二叉搜索树的题目,其实都离不开中序遍历,因为这样就是有序的,迭代法在处理某些情况也是很简单的,因为之间对比数值即可以控制root的左右变化
如果在验证BST的时候:首先在此强调一下二叉搜索树的特性:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
涉及到BST的陷阱:不能单纯的比较左节点小于中间节点,右节点大于中间节点就完事了,而是左子树都小于中间节点,右子树都大于中间节点,因为有可能左子树的右节点比左子树本身的节点大这种情况。
推荐要通过中序遍历(得到有序数组),然后记录前一个数值(pre)和后一个数值比较(cur),得出最值。
在二叉树中通过两个前后指针作比较,会经常用到。
在求众数集合的时候有一个技巧,因为题目中众数是可以有多个的,所以一般的方法需要遍历两遍才能求出众数的集合。
但可以遍历一遍就可以求众数集合,使用了适时清空结果集的方法,这个方法还是很巧妙的。
公共祖先问题:如果找到一个节点,发现左子树出现结点p,右子树出现节点q,或者 左子树出现结点q,右子树出现节点p,那么该节点就是节点p和q的最近公共祖先。此外,实现从底向上遍历判断最好的方式是:后序遍历
二叉树专题总结
到现在已经刷了30+二叉树经典题目,在每一道二叉树的题目中,使用递归三部曲来分析题目,看到二叉树,看到递归,都会想:返回值、参数是什么?终止条件是什么?单层逻辑是什么?
- 涉及到二叉树的构造,无论普通二叉树还是二叉搜索树一定前序,都是先构造中节点。
- 求普通二叉树的属性,一般是后序,一般要通过递归函数的返回值做计算。
- 求二叉搜索树的属性,一定是中序了,要不白瞎了有序性了。
注意在普通二叉树的属性中,我用的是一般为后序,例如单纯求深度就用前序,二叉树:找所有路径 (opens new window)也用了前序,这是为了方便让父节点指向子节点。
随记:刷二叉树专题最后的时候,一直都比较晕晕的,每次遇到递归的时候,都要看着具体例子走一遍才能理解,不能做到深入浅出,宏观上把握,微观上约束,现在有点陷入微观上观察解题,而不注重回归递归的本质,还需要多做题,多总结。
此外,刷题也有一段时间了,今天浅看了一下已经刷了65道题了,数量见长的同时遗忘也随之而来,这就是没有做到及时总结的坏处,总是现看现总结,学过了就过了,没有做到很好地整理、反思、记录、总结,这是非常非常重要的,也是很贴合我自己的学习方法,需要坚持总结,坚持复盘,才能行稳致远。
毕设
目前毕设初稿已经基本完成,基本的逻辑框架和核心内容均已写完,预测总页数达到60余页。
尚未完成:
- 绪论中研究工作部分,比较麻烦,一直没来得及整理研究工作的逻辑和发展;
- 文章中几乎所有的图片,都需要重制,保证清晰度,尽可能使用矢量图;
- 最后的实验仿真结果,也是最复杂的地方,还没完成实验仿真,也没法进行结果分析