总结一些常见的算法题目，每一个题目写一行思路，方便大家复习。具体题目的来源是下面的网站。
前序遍历方法一
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer>ans = new ArrayList<>();
if (root == null) return ans;
Stack<TreeNode>st = new Stack<>();
st.add(root);
while (!st.empty()) {
TreeNode node = st.pop();
ans.add(node.val);
if (node.right != null) st.add(node.right);
if (node.left != null) st.add(node.left);
}
return ans;
}
// 方法二
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer>ans = new ArrayList<>();
Stack<TreeNode>st = new Stack<>();
TreeNode node = root;
while (node != null || !st.empty()) {
while (node != null) {
ans.add(node.val);
st.add(node);
node = node.left;
}
node = st.pop();
node = node.right;
}
return ans;
中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer>ans = new ArrayList<>();
Stack<TreeNode>st = new Stack<>();
while (root != null || !st.empty()) {
while (root != null) {
st.add(root);
root = root.left;
}
root = st.pop();
ans.add(root.val);
root = root.right;
}
return ans;
}
后续遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer>ans = new ArrayList<>();
Stack<TreeNode>st = new Stack<>();
TreeNode pre = null;
while (root != null || !st.empty()) {
while (root != null) {
st.add(root);
root = root.left;
}
root = st.pop();
if (root.right == null || root.right == pre) {
ans.add(root.val);
pre = root;
root = null;
} else {
st.add(root);
root = root.right;
}
}
return ans;
}
}
【2，1，0】【1，2，0】是true，但是如果使用if进行出栈，就会成false。
每次只要栈不空，并且栈顶和当前的pop一致，就应该直接出栈。
这个可以由以下三种情况总结出来
前面的最小值，大于nums[n - 1]。所以当大于，l加，当小于r减。
综合上面三种情况，可以使用二分查找。
然后等于的时候
两数之和：
使用hash，需要保证两者下标不相同。使用排序处理唯一的就很简单
如果需要寻找多个，那么hash还是会简单。边存，边处理。
排序寻找多个的情况下，相等一定出现在中间，但是不一定就一组。所以while之后，不能break，而是i++, j–继续寻找下一组相等的。
两数相加：链表中创建新结点，需要使用p，并且p需要每次移动。如果创建新结点就不用了
无重复字符的最长子串：双指针，java使用int[]数组更快
最长回文子串
正则表达式匹配：*的时候，小优化，类似于完全背包问题的优化，可以考虑直接使用dfs进行求解。只有当j不变的时候，匹配多个。
盛水最多的容器：经典双指针。
三数之和。排序、保证数字相等的时候continue就行了。
n / k, n % k就是对应的数字和对应的位数矩阵的路径：
JZ13 机器人的运动范围