算法题目有无穷多,但是解决问题的思路是可以总结的。对于二叉树类型的题目来说,掌握了树的多种遍历方式,就能够解决大部分的算法题。
一、 二叉树的遍历方式
前序遍历、中序遍历、后续遍历,区别在于对当前节点的处理时机。
1 | public void traversal(TreeNode root){ |
层次遍历,可以借助队列一层一层访问,也可以采用层号+深度优先来实现。
1 | # Queue保存每一层的节点 |
1 | # level表示当前访问到哪一层 |
二、二叉树解题逻辑
每个节点都可以有左右子节点,所以一颗二叉树可以看成由多个【root,left,right】这样的子树构成,天然的适合用递归的方法去解决问题。
只要出现了二叉树,就要去想一想问题的解是否可以由root/left/right
三部分递归解决。
比如:LeetCode第100题《相同的树》,给定两个二叉树,编写一个函数来检验它们是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
运用上述思路,如果root部分相同,同时left和right部分也相同,那结果就是true,否则就应该返回false。
1 | public boolean isSameTree(TreeNode p, TreeNode q) { |
再如:LeetCode第101题《对称二叉树》,判断二叉树是否是镜像对称的。
运用上述思路,第一反应就是如果某个节点的left
部分与right
部分是镜像的,那么以该节点为树根的树就是镜像的。要保证左右两部分镜像,即left
部分的左节点与right
部分的右节点镜像,left
部分的右节点与right
部分的左节点镜像。
1 | public boolean isSymmetric(TreeNode root) { |
三、常见题型
可能路径
用一个列表来记录走过的节点,返回之前记得remove最后一个节点
最优路径
如果是从根节点开始的,就简化成可能路径的遍历;
如果不一定经过根节点,就用
root/left/right
三部分做递归;二叉搜索树相关
利用好搜索树的性质,left.val<root.val<right.val
二叉树序列化与反序列化
注意
null
节点也要存储遍历
上面讲过,除了递归,还可以借助stack数据结构用迭代实现