1. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
出处：
https://edu.csdn.net/practice/26818330
代码1： 迭代
import java.util.List; import java.util.Stack; import java.util.Queue; import java.util.Vector; import java.util.Arrays; import java.util.ArrayList; import java.util.LinkedList; public class postorderTraversal { public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点 public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack<TreeNode> nodeStack = new Stack<>(); TreeNode nodeTemp = root; TreeNode preNode = null; while (nodeTemp != null || !nodeStack.isEmpty()) { while (nodeTemp != null) { nodeStack.push(nodeTemp); nodeTemp = nodeTemp.left; } nodeTemp = nodeStack.peek(); if (nodeTemp.right == null || nodeTemp.right == preNode) { nodeTemp = nodeStack.pop(); list.add(nodeTemp.val); preNode = nodeTemp; nodeTemp = null; } else { nodeTemp = nodeTemp.right; } } return list; } } public static TreeNode createBinaryTree(Vector<Integer> vec) { if (vec == null || vec.size() == 0) { return null; } Queue<TreeNode> queue = new LinkedList<>(); TreeNode root = new TreeNode(vec.get(0)); queue.offer(root); int i = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int j = 0; j < size; j++) { TreeNode node = queue.poll(); if (i < vec.size() && vec.get(i) != NULL) { node.left = new TreeNode(vec.get(i)); queue.offer(node.left); } i++; if (i < vec.size() && vec.get(i) != NULL) { node.right = new TreeNode(vec.get(i)); queue.offer(node.right); } i++; } } return root; } public static void main(String[] args) { Solution s = new Solution(); Integer[] nums = {1,NULL,2,3}; Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums)); TreeNode root = createBinaryTree(vec); System.out.println(s.postorderTraversal(root)); Integer[] nums2 = {3,9,20,NULL,NULL,15,7}; vec = new Vector<Integer>(Arrays.asList(nums2)); root = createBinaryTree(vec); System.out.println(s.postorderTraversal(root)); } }
代码2： 递归
import java.util.List; import java.util.Queue; import java.util.Vector; import java.util.Arrays; import java.util.ArrayList; import java.util.LinkedList; public class postorderTraversal { public final static int NULL = Integer.MIN_VALUE; //用NULL来表示空节点 public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public static class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); postorderTraversalHelper(root, list); return list; } public void postorderTraversalHelper(TreeNode node, List<Integer> list) { if (node == null) { return; } postorderTraversalHelper(node.left, list); postorderTraversalHelper(node.right, list); list.add(node.val); } } public static TreeNode createBinaryTree(Vector<Integer> vec) { if (vec == null || vec.size() == 0) { return null; } Queue<TreeNode> queue = new LinkedList<>(); TreeNode root = new TreeNode(vec.get(0)); queue.offer(root); int i = 1; while (!queue.isEmpty()) { int size = queue.size(); for (int j = 0; j < size; j++) { TreeNode node = queue.poll(); if (i < vec.size() && vec.get(i) != NULL) { node.left = new TreeNode(vec.get(i)); queue.offer(node.left); } i++; if (i < vec.size() && vec.get(i) != NULL) { node.right = new TreeNode(vec.get(i)); queue.offer(node.right); } i++; } } return root; } public static void main(String[] args) { Solution s = new Solution(); Integer[] nums = {1,NULL,2,3}; Vector<Integer> vec = new Vector<Integer>(Arrays.asList(nums)); TreeNode root = createBinaryTree(vec); System.out.println(s.postorderTraversal(root)); Integer[] nums2 = {3,9,20,NULL,NULL,15,7}; vec = new Vector<Integer>(Arrays.asList(nums2)); root = createBinaryTree(vec); System.out.println(s.postorderTraversal(root)); } }
输出：
[3, 2, 1]
[9, 15, 7, 20, 3]
2. 删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s由小写英文字母以及括号'('和')'组成s中至多含20个括号
出处：
https://edu.csdn.net/practice/26818331
代码：
import java.util.List; import java.util.Set; import java.util.HashSet; import java.util.ArrayList; public class removeInvalidParentheses { public static class Solution { private Set<String> set; private String input; private int maxLen = 0; public List<String> removeInvalidParentheses(String s) { set = new HashSet<>(); input = s; removeInvalidParentheses(0, "", 0, 0); return new ArrayList<>(set); } private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount) { if (leftCount < rightCount) { return; } if (index == input.length()) { if (leftCount == rightCount) { if (maxLen < valid.length()) { maxLen = valid.length(); set.clear(); set.add(valid); } else if (maxLen == valid.length()) { set.add(valid); } } return; } char c = input.charAt(index); if (c == '(') { removeInvalidParentheses(index + 1, valid, leftCount, rightCount); removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount); } else if (c == ')') { removeInvalidParentheses(index + 1, valid, leftCount, rightCount); removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1); } else { removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount); } } } public static void main(String[] args) { Solution sol = new Solution(); String s = "()())()"; System.out.println(sol.removeInvalidParentheses(s)); s = "(a)())()"; System.out.println(sol.removeInvalidParentheses(s)); s = ")("; System.out.println(sol.removeInvalidParentheses(s)); } }
输出：
[()()(), (())()]
[(a)()(), (a())()]
[]
3. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
- 两个链表的节点数目范围是
[0, 50] -100 <= Node.val <= 100l1和l2均按 非递减顺序 排列
出处：
https://edu.csdn.net/practice/26818332
代码：
import java.util.*; public class mergeTwoLists2 { public static class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public static class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode h = new ListNode(0, null); ListNode p = h; while (l1 != null && l2 != null) { if (l1.val < l2.val) { p.next = l1; p = l1; l1 = l1.next; } else { p.next = l2; p = l2; l2 = l2.next; } } if (l1 != null) { p.next = l1; } else { p.next = l2; } return h.next; } } public static ListNode createLinkedList(int[] nums) { if (nums == null || nums.length == 0) { return null; } ListNode head = new ListNode(nums[0]); ListNode cur = head; for (int i = 1; i < nums.length; i++) { cur.next = new ListNode(nums[i]); cur = cur.next; } return head; } public static void printLinkedList(ListNode head) { ListNode cur = head; while (cur != null) { System.out.print(cur.val + "->"); cur = cur.next; } System.out.println("null"); } public static void main(String[] args) { Solution s = new Solution(); int[] nums1 = {1,2,4}; int[] nums2 = {1,3,4}; ListNode l1 = createLinkedList(nums1); ListNode l2 = createLinkedList(nums2); printLinkedList(l1); printLinkedList(l2); printLinkedList(s.mergeTwoLists(l1,l2)); } }
输出：
1->2->4->null
1->3->4->null
1->1->2->3->4->4->null
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
