剑指offer计划28（搜索与回溯算法困难）-

1.1、题目1

剑指 Offer 37. 序列化二叉树

1.2、解法

这题给我笑死了，我看到题解有个解法，我愿称之为神。

public class Codec {

    private TreeNode root;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        this.root = root;
        return null;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return root;
    }
}

真的是神仙般的人物。
这里serialize是通过BFS遍历实现的，存放到StringBuilder中最终转String返回。
deserialize也是BFS，只不过是反操作。

1.3、代码

public class Codec {
    public String serialize(TreeNode root) {
        if(root == null) return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }

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

2.1、题目2

剑指 Offer 38. 字符串的排列

2.2、解法

回溯的万能模板

def backtrack(...):
    for 选择 in 选择列表:
        做选择
        backtrack(...)
        撤销选择

这里也挺奇怪，居然不是返回list,就定了hashset最后再遍历进字符串数组返回，
注意这里是不重复，所以，创建要给visited数组来判断是否遍历过该字符。

2.3、代码

class Solution {
    HashSet<String> res = new HashSet();
    boolean []visited;
    public String[] permutation(String s) {
        visited = new boolean[s.length()];
        StringBuffer stringb = new StringBuffer();
        back(s,stringb);
        String []resarr = new String[res.size()];
        int i=0;
        for(String a:res){ 
            resarr[i]=a;
            i++;
        }
        return resarr;
    }
    public void back(String s,StringBuffer stringb){
        if(stringb.length()==s.length()) {
            res.add(stringb.toString());
            return;
        }
        for(int i=0;i<s.length();i++){
            if(visited[i]==true) continue;
            stringb.append(s.charAt(i));
            visited[i]=true;
            back(s,stringb);
            visited[i]=false;
            stringb.deleteCharAt(stringb.length()-1);
        }
    }
}