LeetCode lean
- 递归本质也是循环,是通过函数体来进行的循环
- 写出循环退出条件
- 处理逻辑
- 调用函数本身进入下一层递归
- 数据释放
## Java
public void recur(int level, int param) {
// terminator 递归终结条件
if (level > MAX_LEVEL) {
// process result
return;
}
// process current logic 处理当前递归层逻辑
process(level, param);
// drill down 调用下一层递归
recur( level: level + 1, newParam);
// restore current status 清理当前层状态
}
- 找重复部分,执行 for while (循环、迭代)或者recursion (递归)
- 提升数据结构维度(比如一维变成二维)
- 空间换时间
- 树结构是一种非线性的数据结构,树是以分支的关系定义的层次结构(树的结构定义是一个递归定义)
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
- 有且仅有一个称之为根的节点,二叉树每个节点至多只能有两颗子树(无节点则成为空二叉树,只有一个根节点无子树也能称为二叉树)
- 先序遍历(中左右)
- 中序遍历(左中右)
- 后序遍历(左右中)
# | Title | Solution | Difficulty |
---|---|---|---|
145 | Binary Tree Postorder Traversal(二叉树的后序遍历) | Java | Hard |
94 | Binary Tree Inorder Traversal(二叉树的中序遍历) | Java | Medium |
144 | Binary Tree Preorder Traversal(二叉树的前序遍历) | Java | Medium |
- 递归思想
- 设置递归退出条件
- 遍历结点和子结点
# | Title | Solution | Difficulty |
---|---|---|---|
111 | Minimum Depth of Binary Tree(二叉树的最小深度) | Java | Easy |
104 | Maximum Depth of Binary Tree(二叉树的最大深度) | Java | Easy |
- 使用队列先进先出原则保存每一层结点
- 并保存当前层存在的子节点到队列中
# | Title | Solution | Difficulty |
---|---|---|---|
637 | Average of Levels in Binary Tree(二叉树的层平均值) | Java | Easy |
107 | binary-tree-level-order-traversal-ii(二叉树的层次遍历-ii) | Java | Easy |
102 | Binary Tree Level Order Traversal(二叉树的层序遍历) | Java | Medium |
- 由类型相同的数据元素构成的有序集合
- 查找时间复杂度 O(1)
- 增删时间复杂度度 O(n)
- 头尾添加时间复杂度可以看做是 O(1)
- 单链表每个节点只包含一个指针域,也就是指向后继结点
- 根据链表的结点所含指针个数、指针指向和指针连接方式,可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表、双向链表用于实现线性表的链式存储结构,而其他类型链表多用于实现树和图等非线性结构。
- 查找时间复杂度 O(n)
- 增删时间复杂度度 O(1)
class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
// Constructor to create a new node
// Next is by default initialized
// as null
Node(int d) { data = d; }
}
}