Java每日一练(20230429) 二叉树后序遍历、删除无效括号、合并有序链表-阿里云开发者社区

1. 二叉树的后序遍历

给定一个二叉树，返回它的后序遍历。

示例:

输入: [1,null,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 <= 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();
                        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 < 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));
    }
}