LeetCode—剑指 Offer 37、38

剑指 Offer 37. 序列化二叉树、38. 字符串的排列

题目描述：
[37]
请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
[38]
输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
考察重点：
第37题深度遍历实现树–>字符串，如何生成一棵树（采用深度遍历，每一步新建root，并通过返回值给root.Left和root.Right赋值）
第38题先为字符串排序，再按照从前至后进行递归遍历。

第37题

public class Codec {
    
public String makeString(TreeNode root){
    
            if(root == null){
    
                return "n";
            }
            String left = "," + serialize(root.left);
            String right = "," + serialize(root.right);
            return root.val + left + right;
        }
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
    
            String res = makeString(root);
            return res;
        }

        public TreeNode makeTree(ArrayList<String> datas, TreeNode root){
    
            String nowC = datas.get(0);
            datas.remove(0);
            if(!nowC.equals("n")){
    
                root = new TreeNode(Integer.parseInt(nowC));
                root.left = makeTree(datas, root.left);
                root.right = makeTree(datas, root.right);
            }else{
    
                root = null;
            }
            return root;
        }
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
    
            ArrayList<String> datas = new ArrayList<>(Arrays.asList(data.split(",")));
            if(datas.get(0).equals("n")){
    
                return null;
            }
            TreeNode root = new TreeNode(Integer.parseInt(datas.get(0)));
            datas.remove(0);
            root.left = makeTree(datas, root.left);
            root.right = makeTree(datas, root.right);
            return root;
        }
}

第38题

    boolean[] visit;
    ArrayList<String> res;
    int targetLen;
    public int dfs(char[] s, String nowWord){
    
        if(nowWord.length() == targetLen){
    
            res.add(nowWord);
            return 0;
        }
        for(int i = 0;i < targetLen;i ++){
    
            if(visit[i] || (i > 0 && s[i] == s[i-1] && visit[i-1]))
                continue;
            visit[i] = true;
            dfs(s, nowWord + s[i]);
            visit[i] = false;
        }
        return 0;
    }
    public String[] permutation(String s) {
    
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        targetLen = s.length();
        visit = new boolean[targetLen];
        res = new ArrayList<String>();
        dfs(arr, "");
        String[] tt = new String[res.size()];
        return res.toArray(tt);
    }