目录

1. 二叉树的后序遍历

2. 删除无效的括号

3. 合并两个有序链表

每日一练刷题专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

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 postorderTraversal(TreeNode root) {List list = new ArrayList();Stack 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 vec) {if (vec == null || vec.size() == 0) {return null;}Queue 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 vec = new Vector(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(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 postorderTraversal(TreeNode root) {List list = new ArrayList();postorderTraversalHelper(root, list);return list;}public void postorderTraversalHelper(TreeNode node, List list) {if (node == null) {return;}postorderTraversalHelper(node.left, list);postorderTraversalHelper(node.right, list);list.add(node.val);}}public static TreeNode createBinaryTree(Vector vec) {if (vec == null || vec.size() == 0) {return null;}Queue 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 vec = new Vector(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(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 <= 25
• s由小写英文字母以及括号'('和')'组成
• 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 set;private String input;private int maxLen = 0;public List 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 <= 100
• l1和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 ");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/

	Golang每日一练 专栏
	Python每日一练 专栏
	C/C++每日一练 专栏
	Java每日一练 专栏