剑指offer每日一题【序列化二叉树、字符串的排列】

序列化二叉树.

class Codec {
public:

   //通过前序遍历序列化字符串
    void dfs_s(TreeNode* root, string &s)
    {
        if(!root) 
        {
            s += "null ";
            return ;
        }
        s += to_string(root->val) + ' '; 
        dfs_s(root->left, s);
        dfs_s(root->right, s);
    }
    string serialize(TreeNode* root) {
        string s;
        dfs_s(root, s);
        return s;
    }

	//将序列化的字符串构造出一颗二叉树
    TreeNode* dfs_d(string s, int &u)
    {
        if(u == s.size()) return nullptr;
        int k = u;
        while(s[k] != ' ') k++;
       
       	
        if(s[u] == 'n') //如果第一个出现的是null
        {
            u = k + 1 ; //跳到下一个字符
            return nullptr;
        }  
        int val = 0;
        if(s[u] == '-')  //考虑负数情况
        {
        	//i = u + 1：符号不做计算
            for(int i = u + 1; i < k; i++) val = val * 10 + s[i] - '0';
            val = -val;
        }
        else 
        {
            for(int i = u; i < k; i++) val =val * 10 + s[i] - '0';
        }
        u = k + 1;  //跳到下一个字符
        TreeNode* root = new TreeNode(val);//创建根
        root->left = dfs_d(s, u);  //递归创建左右子树
        root->right = dfs_d(s,u);
        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d(data, u);
    }
};

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

字符串的排列.

class Solution {
public:
    void dfs(string &s, int u, vector &res)
    {
        if(u == s.size()) 
        {
            res.push_back(s);  //存放交换完的答案
            return ;
        }

        vector v(100, false); 
        for(int i = u; i < s.size(); i++)
        {
           if(v[s[i]]) continue;  //如果已经交换过那么就跳过
            v[s[i]] = true;  
            
            swap(s[i], s[u]);
            dfs(s, u + 1, res);//递归到下一个字符出现的位置
            swap(s[u], s[i]);
        }
    }
    vector permutation(string s) {
        vector res;
        dfs(s, 0, res);
        return res;
    }
};