基础新手

链表

注意事项

注意保存上下文环境。注意gc，不要有垃圾变量。换头结点注意考虑头

对于链表不要在乎是O(n)还是O(2n)

长短链表互换

习题

K个节点的组内逆序调整 ?

leetcode：K 个一组翻转链表

找n函数

逆转函数

第一组是否找齐

之后每组处理：start先指向下一组头，遍历完再指向尾

不在于算法，而在于coding能力

链表相加

注意长短链表互换，链表1结点+链表2结点+进位，注意最后进位需要补结点

阶段1：两个相加+进位 while(shortNode != null)

阶段2：单个链表+进位 while(longNode != null)

阶段3：链表结束，仍有进位，补结点 if(carry != 0)

上面三个阶段分别是3个循环

有序链表合并

注意换头，有一个为空就出循环

合并K个升序链表

leetcode:合并K个升序链表

利用小根堆，注意返回空

m条链表，总结点n个。时间复制度 O(log(m)*n)

class Solution {class PackageNode {ListNode node;Integer index;public PackageNode(ListNode node, Integer index) {this.node = node;this.index = index;}}public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}ListNode head = null;ListNode p = head;PriorityQueue<PackageNode> priorityQueue = new PriorityQueue<>(lists.length, Comparator.comparingInt(a -> a.node.val));for (int i = 0; i < lists.length; i++) {if (lists[i] != null) {priorityQueue.add(new PackageNode(lists[i], i));lists[i] = lists[i].next;}}while (priorityQueue.size() > 0) {PackageNode packageNode = priorityQueue.poll();Integer index = packageNode.index;if (lists[index] != null) {priorityQueue.add(new PackageNode(lists[index], index));lists[index] = lists[index].next;}if (head == null) {head = packageNode.node;p = head;} else {p.next = packageNode.node;p = p.next;}}return head;}
}

树

注意事项

对于全都遍历的，使用递归很方便

习题

判断两棵树是否相同

leetcode:相同的树

注意异或^的使用，只有一个成立时为真

对于全都遍历的，使用递归很方便！！！

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {ArrayList<TreeNode> list1 = new ArrayList<>();ArrayList<TreeNode> list2 = new ArrayList<>();list1.add(p);list2.add(q);while (!list1.isEmpty() && !list2.isEmpty()) {p = list1.remove(0);q = list2.remove(0);if (p == null && q == null) {continue;} else if (p != null ^ q != null) {return false;}if (p.val != q.val) {return false;}if (p.left != null && q.left != null) {list1.add(p.left);list2.add(q.left);} else if (p.left == null ^ q.left == null) {return false;}if (p.right != null && q.right != null) {list1.add(p.right);list2.add(q.right);} else if (p.right == null ^ q.right == null) {return false;}}return list1.isEmpty() && list2.isEmpty();}
}

判断树是否是镜面树

leetcode:对称二叉树

虽然是简单，但是也做了不少时间

传两个头结点(left,right)！！！我又用了层序遍历

判断left.val == right.val && fun(left.left, right.right) && fun(left.right, right.left)

class Solution {public boolean isSymmetric(TreeNode root) {return isSymmetric(root, root);}public boolean isSymmetric(TreeNode p, TreeNode q) {if (p == null ^ q == null) {return false;}if (p == null && q == null) {return true;}return p.val == q.val && isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);}public boolean isSymmetricLevel(TreeNode root) {if (root == null) {return true;}ArrayList<TreeNode> treeList = new ArrayList<>();treeList.add(root);while (!treeList.isEmpty()) {if (treeList.size() > 1 && (treeList.size() & 1) != 0) {return false;}int len = treeList.size();for (int i = 0; i < len >> 1; i++) {int leftIndex = len - i - 1;if (treeList.get(i) == null ^ treeList.get(leftIndex) == null) {return false;}if (treeList.get(i) == null && treeList.get(leftIndex) == null) {continue;}if (treeList.get(i).val != treeList.get(leftIndex).val) {return false;}treeList.add(treeList.get(i).left);treeList.add(treeList.get(i).right);}for (int i = len >> 1; i < len; i++) {if (treeList.get(i) == null) {continue;}treeList.add(treeList.get(i).left);treeList.add(treeList.get(i).right);}for (int i = 0; i < len; i++) {treeList.remove(0);}}return true;}
}

返回树的最大深度

leetcode:二叉树的最大深度

用递归思想代码十分简单。差点又想用层序

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}
}

先序遍历和中序遍历建树

leetcode:从前序与中序遍历序列构造二叉树

没啥说的，常见题

    class Solution {HashMap<Integer, Integer> numSite = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder.length <= 0) {return null;}for (int i = 0; i < inorder.length; i++) {numSite.put(inorder[i], i);}return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);}public TreeNode buildTree(int[] preorder, int preLow, int preHigh, int[] inorder, int inLow, int inHigh) {if (preLow > preHigh) {return null;}TreeNode head = new TreeNode(preorder[preLow]);if (preLow < preHigh) {int index = numSite.get(head.val);head.left = buildTree(preorder, preLow + 1, preLow + (index - inLow), inorder, inLow, index - 1);head.right = buildTree(preorder, preLow + (index - inLow) + 1, preHigh, inorder, index + 1, inHigh);}return head;}}