Leetcode 链表，树，回溯 模板

链表/反转链表 迭代 ListNode reverseList(ListNode head) { ListNode prev null, cur head; while (cur ! null) { ListNode next cur.next; // 1. 先存下一个防断链 cur.next prev; // 2. 反转当前指针 prev cur; // 3. prev 前进 cur next; // 4. cur 前进 } return prev; // prev 是新头 } 递归 ListNode reverseList(ListNode head) { if (head null || head.next null) return head; ListNode newHead reverseList(head.next); // 先反转后面 head.next.next head; // 让后一个节点指回自己 head.next null; // 断开原方向防成环 return newHead; } /快慢指针 ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } boolean hasCycle(ListNode head) { ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) return true; // 相遇 } return false; } 虚拟dummy ListNode dummy new ListNode(0); dummy.next head; ListNode cur dummy; // ... 操作 ... return dummy.next; // 真正的头可能被改返回 dummy.next二叉树DFS/二叉树递归骨架 // 104 最大深度分解型f(node) max(f(left), f(right)) 1 int maxDepth(TreeNode root) { if (root null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; } // 226 翻转二叉树遍历型交换左右子树后递归 TreeNode invertTree(TreeNode root) { if (root null) return null; TreeNode left invertTree(root.left); // 先递归翻转 root.left invertTree(root.right); root.right left; return root; } /直径与 LCA // 543 直径后序每个节点算「左深右深」更新全局最大返回自身深度 int ans 0; int diameter(TreeNode root) { if (root null) return 0; int l diameter(root.left), r diameter(root.right); ans Math.max(ans, l r); // 经过该节点的最长路径 return Math.max(l, r) 1; // 向上返回深度 } // 236 最近公共祖先后序左右各找到一个目标则当前节点即 LCA TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null || root p || root q) return root; TreeNode left lowestCommonAncestor(root.left, p, q); TreeNode right lowestCommonAncestor(root.right, p, q); if (left ! null right ! null) return root; // p、q 分居两侧 return left ! null ? left : right; // 都在同一侧 }回溯/回溯通用框架 ListListInteger res new ArrayList(); void backtrack(int[] nums, ListInteger path, boolean[] used) { if (path.size() nums.length) { // 结束条件选满了 res.add(new ArrayList(path)); // 注意必须 new 一份拷贝 return; } for (int i 0; i nums.length; i) { // 遍历选择列表 if (used[i]) continue; // 跳过已选 path.add(nums[i]); used[i] true; // 【做选择】 backtrack(nums, path, used); // 递归下一层 path.remove(path.size() - 1); used[i] false; // 【撤销选择】 } } /排列 / 组合/子集 // 组合/子集用 start 控制起点避免重复选顺序无关 void backtrack(int[] nums, int start, ListInteger path) { res.add(new ArrayList(path)); // 子集每个节点都是答案 for (int i start; i nums.length; i) { path.add(nums[i]); backtrack(nums, i 1, path); // 传 i1不回头 path.remove(path.size() - 1); } } /含重复元素去重 Arrays.sort(nums); // 先排序让相同元素相邻 void backtrack(int[] nums, int start, boolean[] used, ListInteger path) { // ...收集答案... for (int i start; i nums.length; i) { // 同一层里跳过重复元素前一个相同值没被用说明同层已处理过 if (i start nums[i] nums[i-1]) continue; if (used[i]) continue; // 做选择 / 递归 / 撤销 } }