剑指 Offer 37. 序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]
🔗题目链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof

思路

广度优先遍历（BFS），序列化可通过层序遍历获取左右节点的值，空节点就用字符 'n' 代替；反序列化也是通过层序遍历连接左右节点的值，注意在数组中左右节点的位置是相邻的。

实现代码 

/**
 * 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"]
🔗题目链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

思路

回溯+剪枝

实现代码 

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;
        }
    }
}