[数据结构与算法]剑指offer 2021/8/6

37. 序列化二叉树

代码：

序列化采用层次遍历，root不为空则将左右子树添加进队列。
反序列化首先将输入字符串用’’,“分隔开，然后用指针遍历字符串数组，若不为"null”，则添加进二叉树，否则遍历下一个数组元素。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)  return "[]";
        StringBuilder res = new StringBuilder("[");
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                res.append(node.val+",");
                queue.offer(node.left);
                queue.offer(node.right);
            }else
                res.append("null,");
        }
        return res.deleteCharAt(res.length()-1).append("]").toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]"))  return null;
        String[] s = data.substring(1,data.length()-1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i=1;
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(!s[i].equals("null")){
                node.left=new TreeNode(Integer.parseInt(s[i]));
                queue.offer(node.left);
            }
            i++;
            if(!s[i].equals("null")){
                node.right=new TreeNode(Integer.parseInt(s[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

45. 把数组排成最小的数

代码：

定义放在前面可以使返回值更小的数字为较小的数字，自定义比较方法对数字进行排序。最后将数字由小到大拼接起来。

class Solution {
    public String minNumber(int[] nums) {
        String[] strs=new String[nums.length];
        int i=0;
        for(int num:nums){
            strs[i++]=String.valueOf(num);
        }
        //1.重新定义大于和小于
        //若x+y>y+x则x大于y
        //若x+y<y+x则x小于y
        //即谁"小"谁就应该放在前面
        //对sort自定义排序方法，若x+y>y+x即x大于y时，将x和y互换位置，保证较小的元素在前
        Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
        StringBuilder res = new StringBuilder();
        for(String s:strs){
            res.append(s);
        }
        return res.toString();
    }
}