+关注继续查看

# 1. 二叉树的后序遍历

1

\

2

/

3

https://edu.csdn.net/practice/26818330

import java.util.List;
import java.util.Stack;
import java.util.Queue;
import java.util.Vector;
import java.util.Arrays;
import java.util.ArrayList;
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();
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;
}
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));
}
}

import java.util.List;
import java.util.Queue;
import java.util.Vector;
import java.util.Arrays;
import java.util.ArrayList;
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);
}
}
public static TreeNode createBinaryTree(Vector<Integer> vec) {
if (vec == null || vec.size() == 0) {
return null;
}
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. 删除无效的括号

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<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();
} else if (maxLen == valid.length()) {
}
}
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. 合并两个有序链表

两个链表的节点数目范围是 [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;
}
for (int i = 1; i < nums.length; i++) {
cur.next = new ListNode(nums[i]);
cur = cur.next;
}
}
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};
}
}

1->2->4->null

1->3->4->null

1->1->2->3->4->4->null

|
4月前
|
Java
Java每日一练(20230518) 移除元素、跳跃游戏II、复原IP地址
Java每日一练(20230518) 移除元素、跳跃游戏II、复原IP地址
44 0
|
4月前
|

Java每日一练(20230517) 重复元素、链表重复元素、旋转数组
Java每日一练(20230517) 重复元素、链表重复元素、旋转数组
34 0
|
4月前
|
Java
Java每日一练(20230516) 最小栈、组合总和II、相同的树
Java每日一练(20230516) 最小栈、组合总和II、相同的树
36 0
|
4月前
|

Java每日一练(20230515) 阶乘后的零、矩阵置零、两数相除
Java每日一练(20230515) 阶乘后的零、矩阵置零、两数相除
58 0
|
4月前
|
Java
Java每日一练(20230514) 滑动窗、最大子序和、转罗马数字
Java每日一练(20230514) 滑动窗、最大子序和、转罗马数字
50 0
|
4月前
|

Java每日一练(20230513) 输出最值、盛水容器、旋转数组II
Java每日一练(20230513) 输出最值、盛水容器、旋转数组II
46 0
|
4月前
|
Java 索引
Java每日一练(20230512) 最大间距、串联子串、最长回文子串
Java每日一练(20230512) 最大间距、串联子串、最长回文子串
39 0
|
4月前
|
Java 索引
Java每日一练(20230511) 有效数字、重复元素II、类和子类
Java每日一练(20230511) 有效数字、重复元素II、类和子类
53 0
|
4月前
|
Java 容器
Java每日一练(20230510) 生成器类、螺旋矩阵II、删除链表的重复元素II
Java每日一练(20230510) 生成器类、螺旋矩阵II、删除链表的重复元素II
47 0
|
4月前
|

Java每日一练(20230509) 下一个排列、分隔链表、随机指针链表
Java每日一练(20230509) 下一个排列、分隔链表、随机指针链表
34 0