1、二叉树定义

mark

2、二叉树存储结构

mark

2.1、经典题目代码构建

mark

代码构建:
mark

代码对应的二叉树的图:
mark

一行代码搞定lettcode2236,运行通过;就是考察对二叉树结构的理解:
mark

3、深度优先遍历DFS和广度优先遍历BFS概念

mark

3.1、深入讲解广度优先遍历BFS

mark

树的
广度优先遍历BFS
也可以称之为
层序遍历

mark

mark

队列基础知识
mark

4、万能模板经典题

mark

4.1、LeetCode102

mark

mark

mark

mark

4.2、LeetCode107

和102题相同的模板,代码几乎相同,只需要在最后一行用切片的写法做一个反转即可:
mark

4.3、LeetCode103

题目:
mark

题意:
mark

题解:
只需要在模板的基础上,添加一个Flag标志,标记从左往右或者从右往左即可。
mark

4.4、LeetCode637

这连续几道题,都提到二叉树的

的概念,就可以很明显的考虑到是要用
层序遍历
来做。
题目:
mark

题意:
mark

题解:
基于模板,最后添加元素处改一下,由添加层列表,即(每一层的所有节点),改为添加每一层所有节点的平均值即可。
mark

4.5、LeetCode199

题目:
mark

题意:
mark

题解:
根据题意,实际上这道题问的是每一

的最右边的元素是什么?
所以还是涉及到

的概念,还是要用
层序遍历
来做。然后再每一层取出最右边的元素即可。

基于模板,只改一下最后的添加,由添加层列表,改为添加每一层的最后一个元素即可。
mark

如果不用模板,不用层列表sublist,也可以修改为如下代码:
mark
这样就不用额外的空间去存每一层的所有节点。只在每一层的最后一个节点去判断,然后添加最后一个节点到总的列表。

这道题,不是一个明显的层序遍历的题,但是仔细分析题意,思路转换,还是能结合层序遍历模板来解题的。

4.6、LeetCode513

题目和题意:
mark

题解:
基于模板,只需要改动最终的返回ans,ans的初始化由初始化为list改为初始化为root.val,即初始化为根节点的值。
ans的返回由添加层列表,改为添加层的左侧第一个元素的值。
mark

考虑内存空间的情况,可以进一步优化为如下代码:
1和2都可以解决问题
1、
mark
2、
mark

mark

4.7、LeetCode515

题目和题意:
mark

题解:
模板改最后一行添加层列表的最大值即可。
mark

4.8、LeetCode1161

题目和题意:
这个题目还是需要仔细读一下的:
mark

题解:
1、先解决层号的问题,输出层号
mark

mark

2、题解完成:
mark

考虑到节点值可能为负数的情况,最大层的和level_max_sum的初始化,由初始化为0改为初始化为负无穷-inf或者初始化为第一层的值root.val
mark

mark

对题解优化,尽量不要用标准sum函数api,因为它每次也要全部遍历,比较耗时。
不用sum函数的修改版:
mark

4.9、LeetCode101

题目和题意:
示例1
mark
示例2
mark

题解:
1、
mark

2、题解1中还是有问题,满足示例1图的情况,但是不满足示例2;
修改为如下代码后,同时满足示例1和示例2
mark

4.10、LeetCode1302

题目:
mark

题意:
最深的那层这里就是第四层的7和8、最深的那层的节点就一定是叶子节点。

mark

mark

题解:
修改 4.6、LeetCode513 中的代码,将找左下角节点的值,改为求和即可。
mark

不用sum函数的优化版:
mark

5、总结

最核心知识点:
BFS与队列的关系
mark

leetcode102题引申出的万能模板:
mark

mark

6、练习题

mark


注:
文中截图源自大佬:
闭着眼睛学数理化
课程内容

标签: none

添加新评论