数据结构
链表
JZ6 从尾到头打印链表
方法1.遍历
分析
简单的遍历，收集每个节点的
val，然后对结果翻转，返回
代码
public ArrayList<Integer> printListFromTailToHead(ListNode node) {
ArrayList<Integer> res = new ArrayList<>();
//当前节点只要不是null，就一直在循环里绕
while (node != null) {
//添加结果
res.add(node.val);
//遍历完当前节点后，将当前节点滑动到下一个节点
node = node.next;
}
//翻转结果
Collections.reverse(res);
return res;
}方法2.递归
分析
采用递归的方式，不断进入下一个节点，当到达最后一个节点指向
null时，开始返回出口条件：当节点是
null的时候
代码
ArrayList<Integer> res = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode node) {
dfs(node);
return res;
}
private void dfs(ListNode node) {
if (node == null) return;
//进入下一层
dfs(node.next);
//收集节点
res.add(node.val);
}JZ25 合并两个排序的链表
方法1：递归
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null || list2 == null) return list1 == null ? list2 : list1;
if (list1.val > list2.val) {
list2.next = Merge(list1, list2.next);
return list2;
} else {
list1.next = Merge(list1.next, list2);
return list1;
}
}方法2：迭代
public ListNode Merge(ListNode l1,ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
ListNode head = new ListNode(0);
ListNode node = head;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
node.next = l1;
l1 = l1.next;
} else {
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
if (l1 != null) {
node.next = l1;
} else {
node.next = l2;
}
return head.next;
}JZ18 删除链表的节点
方法1:迭代
public ListNode deleteNode(ListNode head, int val) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, cur = head;
//遍历获取当前节点和当前节点的前一个节点
while (cur != null) {
if (cur.val == val) break;
prev = prev.next;
cur = cur.next;
}
//删除cur节点
prev.next = prev.next.next;
return dummy.next;
}JZ23 链表中环的入口结点
方法1:快慢指针
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode slow = pHead, fast = pHead;
boolean f = false;//标志位
while (fast.next != null && fast.next.next != null) {
//f的标志位要是true的时候，并且slow==fast
//初始时，slow和fast是相等的，如果没有标志位会提前退出
if (slow == fast && f) break;
slow = slow.next;
fast = fast.next.next;
f = true;//设置标志位
}
//如果slow和fast不是同一个节点 或者 slow和fast相同，但是是初始时的slow = pHead, fast = pHead
if (slow != fast || !f) return null;
slow = pHead;//slow回到起点，slow和fast步调一致，第一个相遇的点就是环形链表入口
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}也可以有如下的解法：
public ListNode EntryNodeOfLoop(ListNode pHead) {
if (pHead == null || pHead.next == null) return null;
//开始时 slow和fast错开一个位置
ListNode slow = pHead, fast = pHead.next;
while (fast.next != null && fast.next.next != null) {
if (slow == fast) break;
slow = slow.next;
fast = fast.next.next;
}
//如果这时候不是第一次相遇，而fast已经到链表的末尾了，说明没有环
if (slow != fast) return null;
//头节点开始，且
ListNode cur = pHead;
while (cur != slow.next) {
cur = cur.next;
slow = slow.next;
}
return cur;
}
}树
JZ77 按之字形顺序打印二叉树
方法1.
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if (pRoot == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(pRoot);
int level = 0;
while (!q.isEmpty()) {
int size = q.size();
ArrayList<Integer> sub = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
if (level % 2 == 0) sub.add(cur.val);
else sub.add(0, cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
res.add(new ArrayList<>(sub));
level++;
}
return res;
}JZ82 二叉树中和为某一值的路径(一)
方法1:DFS
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
return dfs(root, sum);
}
private boolean dfs(TreeNode root, int sum) {
//当前节点是叶子节点，开始比较val是否相等
if (root.left == null && root.right == null && root.val == sum) return true;
boolean res = false;
//只要左右子树有一个是true即可
if (root.left != null) res = res || dfs(root.left, sum - root.val);
if (root.right != null) res = res || dfs(root.right, sum - root.val);
return res;
}方法2:递归
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
//当前的节点是叶子节点，比较剩下的sum值是否相等
if (root.left == null && root.right == null) return root.val == sum;
//左右两棵子树只要一个符合即可
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}方法3:BFS
public boolean hasPathSum4th(TreeNode root, int sum) {
if (root == null) return false;
LinkedList<TreeNode> nodeQueue = new LinkedList<>();
LinkedList<Integer> numQueue = new LinkedList<>();
nodeQueue.offer(root);
numQueue.offer(root.val);
while (!nodeQueue.isEmpty()) {
TreeNode curNode = nodeQueue.pop();
Integer curNum = numQueue.pop();
if (curNode.left == null && curNode.right == null && curNum == sum) return true;
if (curNode.left != null) {
nodeQueue.offer(curNode.left);
numQueue.offer(curNum + curNode.left.val);
}
if (curNode.right != null) {
nodeQueue.offer(curNode.right);
numQueue.offer(curNum + curNode.right.val);
}
}
return false;
}JZ34 二叉树中和为某一值的路径(二)
方法1:回溯-递减
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int targetSum) {
dfs(root, targetSum, new ArrayList<>());
return res;
}
private void dfs(TreeNode root, int sum, ArrayList<Integer> sub) {
if (root == null) {
return;
}
sub.add(root.val);
if (root.left == null && root.right == null && sum == root.val) res.add(new ArrayList<>(sub));
dfs(root.left, sum - root.val, sub);
dfs(root.right, sum - root.val, sub);
sub.remove(sub.size() - 1);
}方法2:回溯-累加
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int sum) {
if (root == null) return res;
dfs(root,sum,0,new ArrayList<>());
return res;
}
private void dfs(TreeNode root, int sum, int total, ArrayList<Integer> sub) {
if (root == null) return;
sub.add(root.val);
total += root.val;
if (root.left == null && root.right == null) {
if (sum == total) {
res.add(new ArrayList<>(sub));
}
//这一步是为了移除这个叶子节点的值，不管这个叶子节点是否满足条件
sub.remove(sub.size() - 1);
return;
}
dfs(root.left, sum, total, sub);
dfs(root.right, sum, total, sub);
sub.remove(sub.size() - 1);
}JZ84 二叉树中和为某一值的路径(三)
Map<Integer, Integer> map = new HashMap<>();
public int FindPath(TreeNode root, int sum) {
map.put(0, 1);
return helper(root, sum, 0);
}
private int helper(TreeNode root, int sum, int pathSum) {
int res = 0;
if (root == null) return res;
pathSum += root.val;//路径和加上当前节点的值
//路径和-目标sum的值 的节点，这个节点是多少个，在此基础上累加
res += map.getOrDefault(pathSum - sum, 0);
//将从根节点到当前节点，有多少的路径和等于pathSum存入map
map.put(pathSum, map.getOrDefault(pathSum, 0) + 1);
//探索左右子树
res += helper(root.left, sum, pathSum) + helper(root.right, sum, pathSum);
//回溯过程需要将map的数量-1
map.put(pathSum, map.get(pathSum) - 1);
return res;
}JZ68 二叉搜索树的最近公共祖先
public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
TreeNode res = helper(root, o1, o2);
return res.val;
}
public TreeNode helper(TreeNode root, int p, int q) {
if (root == null || root.val == p || root.val == q) return root;
TreeNode left = helper(root.left, p, q);
TreeNode right = helper(root.right, p, q);
if (left != null && right != null) return root;
if (left != null) return left;
if (right != null) return right;
return null;
}JZ86 在二叉树中找到两个节点的最近公共祖先
思路：
1.left和right都为空，说明root的左右子树中都不包含p和q节点，返回null即可
2.left不为空，right为空，说明p和q不在右子树中（因为右子树为空了），这时，返回left，这里面有下面的两种情况：
p和q都在left即左子树上，而root节点恰好指向了p或者qp和q都在left即左子树上，而root节点未指向了p或者q，指向的是最近公共祖先节点
3.right不为空，left为空，说明p和q不在左子树中（因为左子树为空了），这时，返回right，这里面有下面的两种情况：
p和q都在right即右子树上，而root节点恰好指向了p或者qp和q都在right即右子树上，而root节点未指向了p或者q，指向的是最近公共祖先节点
4.left不为空，并且right不为空，说明p和q分布在root节点的左右子树的两侧，这时root为p和q的最近公共祖先节点，返回
public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
TreeNode res = helper(root, o1, o2);
return res.val;
}
public TreeNode helper(TreeNode root, int p, int q) {
if (root == null || root.val == p || root.val == q) return root;
TreeNode left = helper(root.left, p, q);
TreeNode right = helper(root.right, p, q);
if (left != null && right != null) return root;
if (left != null) return left;
if (right != null) return right;
return null;
}Last updated