# Java每日一练(20230429) 二叉树后序遍历、删除无效括号、合并有序链表

## 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
• l1l2 均按 非递减顺序 排列

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

## 🌟 每日一练刷题专栏 🌟

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

|
2月前
|
Java

15 0
|
1天前
|

LeetCode初级算法题：环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题：环形链表+排列硬币+合并两个有序数组java解法
5 0
|
1天前
|

LeetCode初级算法题：反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题：反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
4 0
|
1月前
|

14 4
|
2月前
|

[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
25 2
|
2月前
|

18 0
|
2月前
|

Java数据结构与算法：双向链表
Java数据结构与算法：双向链表
31 0
|
2月前
|

Java数据结构与算法：循环链表
Java数据结构与算法：循环链表
19 0
|
2月前
|
Java

12 0
|
2月前
|
Java

18 0