1、旧键盘
旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
肯定坏掉的那些键。
输入描述:
输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、
以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。
输出描述:
按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。
示例1
1. 输入 2. 7_This_is_a_test<br/>_hs_s_a_es 3. 输出 4. 7TI
首先我们分析一下思路哈：简单理解一下题目：就是说要让我们输出字符串1没有在字符串2中的部分（也就是字符串1中多出来的那部分，同时每个字符(大写）按照字符串中出现的顺序只可以输出1次即可），所以我们可以写一个方法来实现这个功能：首先我们要把两个字符串都改为大写的字符数组，之后用一个HashSet把s2出现的字符存放起来，然后遍历s1所在的字符数组ch1，如果HashSet中不包含ch1中的元素就把它存放到一个List当中，最后打印List中的内容即可。
AC代码：
1. import java.util.*; 2. public class Main{ 3. 4. public static void main(String[]args){ 5. Scanner scan=new Scanner(System.in); 6. while(scan.hasNextLine()){ 7. String s1=scan.nextLine(); 8. String s2=scan.nextLine(); 9. fun(s1,s2); 10. } 11. } 12. public static void fun(String s1,String s2){ 13. char[]ch1=s1.toUpperCase().toCharArray(); 14. char[]ch2=s2.toUpperCase().toCharArray(); 15. HashSet<Character>set1=new HashSet<>(); 16. for(char x:ch2){ 17. set1.add(x); 18. } 19. List<Character> list=new ArrayList<>(); 20. 21. for(char x:ch1){ 22. if(!set1.contains(x)){ 23. if(!list.contains(x)){ 24. list.add(x); 25. } 26. } 27. } 28. for(char x:list){ 29. System.out.print(x); 30. } 31. } 32. }
2、二叉搜索树与双向链表
描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值0≤val≤1000
要求：空间复杂度O(1)O(1)（即在原树上操作），时间复杂度 O(n)O(n)
注意:
1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
4.你不用输出双向链表，程序会根据你的返回值自动打印输出
输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。
示例1
1. 输入： 2. {10,6,14,4,8,12,16} 3. 返回值： 4. From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4; 5. 说明： 6. 输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
示例2
1. 输入： 2. {5,4,#,3,#,2,#,1} 3. 返回值： 4. From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1; 5. 6. 说明： 7. 5 8. / 9. 4 10. / 11. 3 12. / 13. 2 14. / 15. 1 16. 树的形状如上图
AC代码：
1. /** 2. public class TreeNode { 3. int val = 0; 4. TreeNode left = null; 5. TreeNode right = null; 6. 7. public TreeNode(int val) { 8. this.val = val; 9. 10. } 11. 12. } 13. */ 14. public class Solution { 15. //返回的第一个指针，即为最小值，先定为null 16. public TreeNode head = null; 17. //中序遍历当前值的上一位，初值为最小值，先定为null 18. public TreeNode pre = null; 19. public TreeNode Convert(TreeNode pRootOfTree) { 20. if(pRootOfTree == null) 21. //中序递归，叶子为空则返回 22. return null; 23. //首先递归到最左最小值 24. Convert(pRootOfTree.left); 25. //找到最小值，初始化head与pre 26. if(pre == null){ 27. head = pRootOfTree; 28. pre = pRootOfTree; 29. } 30. //当前节点与上一节点建立连接，将pre设置为当前值 31. else{ 32. pre.right = pRootOfTree; 33. pRootOfTree.left = pre; 34. pre = pRootOfTree; 35. } 36. Convert(pRootOfTree.right); 37. return head; 38. } 39. }
