剑指offer(61-66)编程题

61、请实现两个函数，分别用来序列化和反序列化二叉树。
62、给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。
64、给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

61、请实现两个函数，分别用来序列化和反序列化二叉树。

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

初始：

1 public class Solution {
2     String Serialize(TreeNode root) {
3         
4   }
5     TreeNode Deserialize(String str) {
6        
7   }
8 }

代码：

 1 class TreeNode {
 2     int val = 0;
 3     TreeNode left = null;
 4     TreeNode right = null;
 5 
 6     public TreeNode(int val) {
 7         this.val = val;
 8 
 9     }
10 
11 }
12 
13 public class Solution {
14 
15     // 便于反序列化的操作
16     int index = -1;// 不要 private static int index = -1 ,在牛客网这种写法会报错（非常的奇怪）
17 
18     String Serialize(TreeNode root) {
19 
20         // 创建结果集对象
21         StringBuilder sb = new StringBuilder();
22 
23         // 递归的出口
24         if (root == null) {
25             sb.append("#!");// 序列化时通过某种符号表示空节点（#）
26             return sb.toString();
27         }
28 
29         sb.append(root.val + "!");// 若为非空节点，则输入“值!”
30         sb.append(Serialize(root.left));// 递归序列化左子树
31         sb.append(Serialize(root.right));// 递归序列化右子树
32 
33         return sb.toString();
34     }
35 
36     TreeNode Deserialize(String str) {
37         
38         if (str == null || str.length() == 0) {
39             return null;
40         }
41 
42         String[] arr = str.split("!");// 分隔字符串
43 
44         index++;
45 
46         // 临界值
47         if (index >= arr.length) {
48             return null;
49         }
50 
51         if ("#".equals(arr[index])) {
52             return null;
53         }
54 
55         TreeNode ans = new TreeNode(Integer.parseInt(arr[index]));// 重构二叉树
56         ans.left = Deserialize(str);
57         ans.right = Deserialize(str);
58 
59         return ans;
60 
61     }
62 }

62、给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。

思路：对于一个二叉搜索树而言，如果进行中序遍历，就可以获得从小到大排列的结点序列，然后只需返回指定的第k小的结点即可。

 1 import java.util.ArrayList;
 2 
 3 class TreeNode {
 4     int val = 0;
 5     TreeNode left = null;
 6     TreeNode right = null;
 7 
 8     public TreeNode(int val) {
 9         this.val = val;
10 
11     }
12 
13 }
14 
15 public class Solution {
16 
17     ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
18 
19     TreeNode KthNode(TreeNode pRoot, int k) {
20 
21         // 中序遍历
22         InOrder(pRoot);
23 
24         if (k <= 0 || k > ans.size()) {
25             return null;
26         }
27 
28         // 返回第k小的数
29         return ans.get(k - 1);
30 
31     }
32 
33     // 中序遍历
34     public void InOrder(TreeNode root) {
35 
36         if (root == null) {
37             return;
38         }
39 
40         InOrder(root.left);
41         ans.add(root);
42         InOrder(root.right);
43     }
44 
45 }

64、给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

分析：这道题注意通过滑动窗口的大小和数组的长度确认总轮数，为 num.length - size +1 次。然后比较每轮的最大值，比较过程可以借用选择排序思想。

 1 import java.util.ArrayList;
 2 
 3 public class Solution {
 4     public ArrayList<Integer> maxInWindows(int[] num, int size) {
 5 
 6         // 结果集对象
 7         ArrayList<Integer> ans = new ArrayList<Integer>();
 8 
 9         if (num == null || num.length == 0 || size == 0 || size > num.length) {
10             return ans;
11         }
12 
13         // 存储每次窗口中的最大值
14         int curMax = 0;
15 
16         for (int i = 0; i <= num.length - size; i++) {// 控制轮数
17 
18             curMax = num[i];
19             for (int j = i; j < i + size; j++) {
20                 if (num[j] > curMax) {
21                     curMax = num[j];
22                 }
23             }
24 
25             // 加入到结果集当中
26             ans.add(curMax);
27         }
28         return ans;
29     }
30 }

方式二：

 1 import java.util.ArrayList;
 2 import java.util.Arrays;
 3 
 4 public class Solution {
 5     public ArrayList<Integer> maxInWindows(int[] num, int size) {
 6 
 7         // 创建结果集对象
 8         ArrayList<Integer> ans = new ArrayList<Integer>();
 9 
10         if (size == 0) {
11             return ans;
12         }
13 
14         for (int i = 0; i < num.length - size + 1; i++) {
15             int val = getMax(num, i, i + size);
16             ans.add(val);
17         }
18 
19         return ans;
20     }
21 
22     public static int getMax(int[] num, int x, int y) {
23         int[] arr = Arrays.copyOfRange(num, x, y); //包头不包尾
24         Arrays.sort(arr);
25         return arr[arr.length - 1];
26     }
27 }