4/11-剑指offer

1.二叉搜索树与双向链表
思路：二叉搜索树中序遍历是排好序的，按照中序遍历的顺序，当遍历转换到根节点时，左子树已经转换为一个排序的链表，并且处在链表中的最后一个节点是当前值最大的节点。我们把倒数第二个节点和根节点连接起来，此时链表的最后一个节点就是根节点。接着去遍历转换右子树，并把根节点和右子树中最小的节点连接起来。考虑使用递归。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode *Last=nullptr;//指向链表最后一个节点
        helper(pRootOfTree,&Last);
        TreeNode *Head=Last;
        while(Head!=nullptr&&Head->left!=nullptr)
        {
            Head=Head->left;//返回头结点
        }
        return Head;
    }
    void helper(TreeNode* pNode,TreeNode** Last)//注意参数写法
    {
        if(pNode==nullptr) return;
        TreeNode *cur=pNode;
        if(cur->left!=nullptr)
            helper(cur->left,Last);//遍历左子树
        cur->left=*Last;//根节点左指针指向左子树最大的数（右叶子）
        if(*Last!=nullptr)
            (*Last)->right=cur;//右叶子不为空，其右指针指向根节点
        *Last=cur;//为空，直接等于根节点
       if(cur->right)
            helper(cur->right,Last);//遍历右子树
    }
};

2.序列化二叉树
思路：前序遍历序列化，利用递归。反序列化同样使用递归，如果输入不是数字，说明此节点为null，跳过；如果是数字，进行反序列化递归。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> buf;
    void dfs1(TreeNode *root) {
        if(!root) buf.push_back(0xFFFFFFFF);
        else {
            buf.push_back(root->val);
            dfs1(root->left);
            dfs1(root->right);
        }
    }
    TreeNode* dfs2(int* &p) {
        if(*p==0xFFFFFFFF) {
            p++;
            return NULL;
        }
        TreeNode* res=new TreeNode(*p);
        p++;
        res->left=dfs2(p);
        res->right=dfs2(p);
        return res;
    }
    char* Serialize(TreeNode *root) {
        buf.clear();
        dfs1(root);
        int bufSize=buf.size();
        int *res=new int[bufSize];
        for(int i=0;i<bufSize;i++) res[i]=buf[i];
        return (char*)res;
    }
    TreeNode* Deserialize(char *str) {
        int *p=(int*)str;
        return dfs2(p);
    }
};

3.字符串的排列
思路：把字符串分成两部分，一部分是字符串的第一个字符，另一部分是第一个字符以后的所有字符；然后求阴影部分（除第一个字符）的子字符串的排列（递归）；然后拿第一个字符和它后面的字符逐个交换。

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> result;
        if(str.empty()) return result;
        exChange(str,result,0);
        sort(result.begin(),result.end());
        return result;     
    }
    void exChange(string str,vector<string> &result,int begin)
    {
        if(begin==str.size()-1)
        {
            if(find(result.begin(),result.end(),str)==result.end())
            {
                result.push_back(str);//不重复的放进去
            }

        }
        else
        {
          for(int i=begin;i<str.size();i++)
           {
            swap(str[i],str[begin]);
            exChange(str,result,begin+1);//递归排列剩下的序列
            swap(str[i],str[begin]);//换回来再换回去
            }  
        }

    }
    void swap(char &x,char &y)
    {
        char z;
        z=x;
        x=y;
        y=z;
    }
};