安橙的博客

二叉树的层序遍历 题目 思路 put root into a queue queue is not empty 2.1. size = queue.size(), this is exactly how many nodes are in the current level. 2.1. repeat size times: * pop one node from queue * add its value to level * add left and right child Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Deque<TreeNode> q = new ArrayDeque<>(); q.offer(root); while(!q.isEmpty()) { int size = q.size(); List<Integer> level = new ArrayList<>(size); for (int i = 0; i < size; i ++) { TreeNode node = q.poll(); level.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } res.add(level); } return res; } }

题目 Solution The longest path through that node equals: left subtree depth + right subtree depth. the longest path must pass through some node as a highest point. ...

将有序数组转换为二叉搜索树 题目 思路 A height-balance BST is achieved by always picking the middle element as the root. The left and right subtree sizes differ by at most 1. ...

验证二叉搜索树 题目 思路 root starts with (-inf, +inf) left child inherits (min, root.val) right child inherits (root.val, max) Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public boolean isValidBST(TreeNode root) { return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean dfs(TreeNode node, long low, long high) { if (node == null) { return true; } long v = node.val; if (v <= low || v >= high) { return false; } return dfs(node.left, low, v) && dfs(node.right, v, high); } }

题目 思路 找中点并每次拆分链表 递归排序 合并两个有序链表 Java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode mid = splitMid(head); ListNode left = sortList(head); ListNode right = sortList(mid); return merge(left, right); } private ListNode splitMid(ListNode head) { ListNode slow = head, fast = head, prev = null; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; return slow; } private ListNode merge(ListNode a, ListNode b) { ListNode dummy = new ListNode(0), p = dummy; while (a != null && b != null) { if (a.val <= b.val) { p.next = a; a = a.next; } else { p.next = b; b = b.next; } p = p.next; } p.next = (a != null) ? a : b; return dummy.next; } }

题目 思路 O(1) 查询 (哈希表) 记录最近使用顺序 (链表) 需要组合哈希表 + 双向链表 Java 解法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 class LRUCache { private static class Node { int key, val; Node prev, next; Node(int k, int v) { key = k; val = v; } } private final int capacity; private final Map<Integer, Node> map = new HashMap<>(); private final Node head = new Node(0, 0); private final Node tail = new Node(0, 0); public LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } public int get(int key) { Node node = map.get(key); if (node == null) { return -1; } moveToHead(node); return node.val; } public void put(int key, int value) { Node node = map.get(key); if (node != null) { node.val = value; moveToHead(node); return; } Node n = new Node(key, value); map.put(key, n); addAfterHead(n); if (map.size() > capacity) { Node lru = removeTail(); map.remove(lru.key); } } private void moveToHead(Node node) { remove(node); addAfterHead(node); } private void addAfterHead(Node node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private Node removeTail() { Node node = tail.prev; remove(node); return node; } }

题目 思路 dfs 值相等，且 left.left 对 right.right，left.right 对 right.left bfs ...

题目 思路 递归解法 递归遍历左子树 访问当前答案 递归遍历右子树 迭代 + 栈解法 ...