「剑指Offer」Day28：搜索与回溯算法（困难）

/**
 * 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 null;
        StringBuffer nodeStr = new StringBuffer();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        nodeStr.append(root.val + ","); //以逗号分割各节点的值
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i<size; i++){
                TreeNode curr = queue.poll();
                if(curr.left != null){ //不为空就入队，拼接
                    queue.offer(curr.left);
                    nodeStr.append(curr.left.val + ",");
                }else{
                    nodeStr.append("n,"); //为空就拼接 n,
                }
                if(curr.right != null){
                    queue.offer(curr.right);
                    nodeStr.append(curr.right.val + ",");
                }else{
                    nodeStr.append("n,");
                }
            }
        }
        return nodeStr.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) return null;
        String[] nv = data.split(","); //根据逗号分割字符串
        TreeNode root = new TreeNode(Integer.parseInt(nv[0])); //取第一个元素作为根节点
        Queue<TreeNode> queue = new LinkedList<>(); //使用队列实现层序遍历连接左右节点
        queue.offer(root);
        for(int i = 1; i < nv.length; i++){
            if(!queue.isEmpty()){
                TreeNode curr = queue.poll();
                if(!"n".equals(nv[i])){ //左节点不为空就连接，并入队
                    curr.left = new TreeNode(Integer.parseInt(nv[i]));
                    queue.offer(curr.left);
                }else{
                    curr.left = null;
                }
                if(!"n".equals(nv[i + 1])){ //当前节点的左右节点在数组中是相连的
                    curr.right = new TreeNode(Integer.parseInt(nv[i+1]));
                    queue.offer(curr.right);
                }else{
                    curr.right = null;
                }
                i = i + 1; //一次处理了数组中两个节点
            }
        }
        return root;
    }
}

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

剑指 Offer 38. 字符串的排列

输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]

class Solution {
    public String[] permutation(String s) {
        List<String> list = new ArrayList<>();
        char[] cArr = s.toCharArray(); //将字符串转换为字符数组
        Arrays.sort(cArr); //排序，这样重复元素会聚集在一起
        boolean[] visited = new boolean[s.length()]; //标记访问过的位置
        backtrack(cArr, "", list, visited);
        return list.toArray(new String[0]); //将集合转换为数组
    }
    public void backtrack(char[] cArr, String s, List<String> list, boolean[] visited) {
        if (s.length() == cArr.length) { //递归终止条件
            list.add(s);
            return;
        }
        for (int i = 0; i < cArr.length; i++) {
            if (visited[i]) continue;
            //若当前元素与前一个元素相等，且前一元素未被访问过，就直接跳过，避免重复排列
            if (i > 0 && cArr[i] == cArr[i-1] && !visited[i-1]){
                continue;
            }
            visited[i] = true;
            //递归访问没访问过的位置
            backtrack(cArr, s + String.valueOf(cArr[i]), list, visited);
            //在回溯过程中还原到上一状态，直接拼接字符串为两个不同的对象，不用还原
            visited[i] = false;
        }
    }
}