链表
No.203--移除链表元素--简单
链接:移除链表元素
代码:
1 | class Solution { |
- 使用虚拟头节点是链表类题目的常见操作,用于解决头节点与其他节点处理细节不一致的问题。虽然不使用虚拟头节点也完全可以解决,但是为了逻辑的一致性,我将统一使用虚拟头节点。
- 保留当前处理节点cur的上一个节点pre的可访问性通常是有意义的。
No.206--反转链表--简单
链接:反转链表
递归法:
1 | class Solution { |
- 使用递归,递归函数的作用要明确:输入一个头节点,将此头节点及之后的所有节点反转,返回值是新的头节点。
- 每一层递归,只需要将当前节点的后面节点其余节点反转,反转后的新的末尾连上当前节点,当前节点的下一节点指向null即可。
迭代法
1 | class Solution { |
- 仅考虑当前节点cur,要做的无非是将下一跳指向前一节点pre,然后整体往后移动,处理下一个节点。
- 为了在改变当前节点下一跳之后,还能准确的迭代到原下一节点,需要在改变前提前将下一节点获取到。
No.24--两两交换链表中的节点--中等
链接: 两两交换链表中的节点
递归法
1 | class Solution { |
迭代法
1 | class Solution { |
- 跟之前的思路差不多,可递归可迭代,只不过每次步进两个节点。
No.19--删除链表的倒数第N个节点--中等
链接:删除链表的倒数第 N 个结点
代码:
1 | class Solution { |
- 虚拟头节点的使;
- 快慢指针,快的先走n步;
- while中为什么是fast.next != null:这样循环结束时,fast在最后一个节点,slow在倒数第n个节点的前一个,这样才方便删除倒数第n个节点。如果fast指向末尾null,slow刚好到了倒数第n个节点,不方便删除。
No.面试题02.07--链表相交--简单
链接:链表相交
代码:
1 | public class Solution { |
- 两个指针从各自头出发,步进1,走完自己的转去另一个链的头继续,两指针相同时,为null说明全走完了没相遇,不为null说明走到了公共节点(总长都是a+b,公共节点之后长度c,两指针一直以同样的速度走,一定会在a+b-c步时相遇)。
No.142--环形链表 II--中等
链接:环形链表 II
代码:
1 | public class Solution { |
- 快慢指针;
- 快指针每次走2,慢指针每次走1,第一次相遇后,两指针分别从head和相遇点出发,均每次走1,再次相遇即为环起点;
- fast不论任何时候走不下去了(由于null),一定是不存在环。
二叉树
No.226--翻转二叉树--简单
链接:翻转二叉树
递归法:
1 | class Solution { |
- 抽象起来其实每一层都和交换两个变量a和b的值差不多,写法也是借用tmp,三行搞定…只不过变量的值是子树的根节点。
迭代法:
1 | class Solution { |
- 把前序遍历的读值操作改为对当前节点的左右交换操作,遍历完一遍,那么每个节点都刚好被且仅被翻转了一次。
No.101--对称二叉树--简单
链接:对称二叉树
代码:
1 | class Solution { |
- 判断一颗树是不是对称二叉树,看看左右子树是否互相对称(注意不是自己对称),而左右两子树互相对称,需要满足三个条件:
- 左右两子树的根节点值一样
- 左子树的左子树和右子树的右子树互相对称
- 左子树的右子树和右子树的左子树互相对称
- 因此,本题实质上是从第二层开始递归的。
- 重点是理解
两子树互相对称
和一个树是对称二叉树
的区别。
No.104--二叉树的最大深度--简单
链接:二叉树的最大深度
递归法:
1 | class Solution { |
- 二叉树的最大深度,就是左右子树最大深度的大者+1.
No.111--二叉树的最小深度--简单
链接:二叉树的最小深度
递归法:
1 | class Solution { |
- 与No.104题类似,但是不能直接简单的把max换成min,如果某个子树小到极限0,意味着这边不是叶子节点,结果仅有另一边决定。
No.222--完全二叉树的节点个数--中等
链接:完全二叉树的节点个数
代码:
1 | class Solution { |
- 为提高计算效率,要充分利用完全二叉树的特性,因此不再考虑常规二叉树计算节点个数的办法;
- 完全二叉树可以拆分成多个满二叉树,而满二叉树可以直接根据层数计算节点个数;
- 因此,从根节点开始递归,递归过程中,若当前二叉树是满二叉树直接计算,不是的话继续拆分;
- 判断是满二叉树,就看一路向左和一路向右的路是否一样长(前提是已知是完全二叉树)。
No.110--平衡二叉树--简单
这真能算简单?
链接:平衡二叉树
自顶向下递归:
1 | class Solution { |
- 这种递归比较好理解,与平衡二叉树的定义完全一致,但是存在重复计算。不同的isBalanced调用中,对同一个节点的height计算是重复的,可以优化为如下自底向上的递归过程。
自底向上递归:
1 | class Solution { |
- 这种递归,只有一个height函数是在递归调用的,递归的过程本质上是自底向上推出每一个节点的高度,不存在重复计算。
- 在这一过程中捎带地判断是否平衡是很有必要的,仅仅知道左右子树高度、而不知道左右子树是否平衡,是不足以判断当前树是否平衡的。
No.257--二叉树的所有路径--简单
这还是简单?
链接:二叉树的所有路径
代码:
1 | class Solution { |
- 这是递归法一种比较简单的写法,之前的状态不用全局变量来维护,而是直接用一个新的值传进来,这样不用考虑回溯之后撤销影响的问题,每次传到一次递归调用的,都是目前已知路径的一个新变量tmp。
- 此处递归函数的含义:当前处理节点root,从原根节点到目前节点之父的路径已知是s,该如何操作,即:把当前节点拼到串上,生成作为已知路径,剩下的交给左孩子和右孩子分别处理。