序列化二叉树

Hard 原题连接：序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

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

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

解题思路

  1. 如何序列化二叉树（以什么顺序序列化）
    1. 先序遍历：根 （左）（右）的顺序，根（根左右）（根左右）,可以确定当前第一个是根节点，遍历左子树，直到叶子节点，之后是右子树
    2. 中序遍历：（左） 根 （右）的顺序，很难判断出根节点的位置，
    3. 后序遍历：（左）（右） 根 的顺序，同上不便判断出根节点和左右节点之间的区分
  2. 二叉树有几种状态需要区别
    1. 当前节点：直接把值当字符存储，空节点（叶子节点的子节点）使用特殊字符存储 “#”
    2. 子节点与根：使用字符连接，便于反序列化时区分各个值 “-”

综上，序列化使用先序遍历，判断是否是null，存储当前值，遍历左子树，遍历右子树

反序列化则是按顺序读取序列化的值，凭借自己拆分的字符，拆成一个个数字，按先序连接

Java代码

/**
 * 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 sb = new StringBuilder();
        sb.append(root.val);
        sb.append("_");
        sb.append(serialize(root.left));
        sb.append("_");
        sb.append(serialize(root.right));
        String str = sb.toString();
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] values = data.split("_");
        Queue<String> queue = new LinkedList<>();
        for(int i = 0; i < values.length; i++) {
            queue.add(values[i]);
        }
        return reconOrder(queue);
    }

    //组成树
    public static TreeNode reconOrder(Queue<String> queue) {
        String value = queue.poll();
        if(value.equals("#")){
            return null;
        }
        TreeNode head = new TreeNode(Integer.valueOf(value));
        head.left = reconOrder(queue);
        head.right = reconOrder(queue);
        return head;
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

字符串的排列

medium 原题连接：字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例：

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

解题思路

字符的所有排列，理论上，一个长度为n的字符最大排列数应该是 !n 个，但是例子中发现存在重复字符，比如 abb

思路变为每一个字符在每一个位置只能出现一次（每一个位置都设置一个hashset存储已经在这个位置站过的字符）

第一个位置会遍历n次，第二位置会遍历n-1次….最后位会遍历1次，总计 !n 次

但是，一旦出现已经在某个位置重复选过，剪枝

直至拼接长度到达目标长度

Java代码

class Solution {
    // 1.用什么存储
    char[] sortStr;
    List<String> ans = new LinkedList<>();

    public String[] permutation(String s) {
        // 2.初始化：String 转 charArray
        sortStr = s.toCharArray();
        dfs(0);
        return ans.toArray(new String[ans.size()]);
    }
    
    // 3.dfs遍历运算，终止条件是什么，dfs如何递归
    public void dfs(int index) {
        // 4.剪枝条件
        if(index == sortStr.length-1) {
            ans.add(String.valueOf(sortStr));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i=index; i<sortStr.length; i++) {
            if(set.contains(sortStr[i]))continue;
            set.add(sortStr[i]);
            swap(i, index);
            dfs(index + 1);
            swap(i, index);
        }
        return;
    }

    // 5.交换函数
    public void swap(int a, int b) {
        char mid = sortStr[a];
        sortStr[a] = sortStr[b];
        sortStr[b] = mid;
    } 
}