树并不是一个线性的数据结构，我们很难把树变成一条线。
遍历一棵树！
preOrder
leetcode 104: 树的深度？
leetcode 101: 数是否镜像对称？
leetcode 100: 两棵树是否完全一致?
leetcode 951: 翻转等价二叉树?
Binary Search Tree
leetcode 99: 判断是否是合理的BST?
作者： Hanyuuu
-
Class 3 Queue, Stack, Linked List
Queue
FIFO first in first out 只要满足先进先出，那就是一个queue
Stack: push(),pop(),top()
LIFO last in first out
怎么用两个stack来模拟一个queue呢？
Solution:
Stack1: for new element, push to stack1
Stack2: to pop out 1st element:
Case1: if stack2 is empty, then we move all the element from stack1 to stack2, then pop from stack2
Case2: if stack2 is not empty, then just pop from stack2
Time: Push O(1), Pop O(n)
But when we consisdered Amortized time complexity of Pop() = O(1)
怎么用stack来实现时间复杂度为O(1)的min()函数？
Solution:
keep the add() and remove() in sync between stack1 and stack2
Stack1: for new element, push to stack1
Stack2: to push new element:
Case1: if stack2 is empty, then we push same element to stack2.
Case2: if stack2 is not empty, then we check if new element is smaller then stack2.top(), if so, push new element to stack2, else push stack2.top() to stack2.
Follow up question: 怎么优化空间复杂度，假设很多stack1内的元素是重复元素。
那么只需要再stack2中存push入这个数时的stack1的size即可，即说明stack1对应这个最小数时的index。
怎么用多个stack来排序数字?
怎么用多个stack来编写一个de-queue?
期望O(1)的摊销时间复杂度。
逆波兰表达式(stack的实践)
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for(String token: tokens){
switch (token){
case “+” -> {
int right = stack.pop();
int left = stack.pop();
stack.push(right + left);
}
case “-” -> {
int right = stack.pop();
int left = stack.pop();
stack.push(left – right);
}
case “*” -> {
int right = stack.pop();
int left = stack.pop();
stack.push(left * right);
}
case “/” -> {
int right = stack.pop();
int left = stack.pop();
stack.push(left / right);
}
default -> stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
Linked List
When you want to de-reference a ListNode, make sure it is not a NULL pointer
Never ever lost the control of the head pointer of the LinkedList.
经典题目：
反转链表
怎么找到linked list中间的node: 快慢指针
快慢指针来判定一个linkedlist是否有环
怎么在一个sorted linked list insert 一个node
merge 两个sorted linkedlist into one long sorted linked list
N1 -> N2 ->N3 -> … – > Nn Leetcode 147
N1 -> Nn -> N2 -> Nn-1
-
每天和一个人交流Day0
我叫阿娟，
这是我的第一篇blog，我本来还想要不要起一个足够吸引眼球的标题，但想了想还是简简单单记录实际最好了。 简单来说，这是我正在做的一个类似采访的项目，每天和一个人交流，聊任何内容任何题目都有可能。
当然，我本人还是一个计算机专业的学生，我也不止会track这一个项目在这里，anyway，这是Day0，算是一个对这个项目的预告，我希望这会是一个有意思的项目，并得到一个至少让我自己满意的结果。
这里是阿娟，祝我自己好运。
07.22.2026