剑指 Offer 36. 二叉搜索树与双向链表

题解：

思路很简单，就是一个中序遍历，一边遍历一边把节点连接起来。

代码：

class Solution {
public:
    Node  *pre,*head;
    void dfs(Node* root){
        if(root==nullptr) return;
        dfs(root->left);
        if(pre==nullptr) head=root;//这是个头节点
        else 
            pre->right=root;
        root->left=pre;
        pre=root;
        dfs(root->right);
    }
 
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return root;
        dfs(root);
        head->left=pre;
        pre->right=head;
        return head;
    }
};

结果：

剑指 Offer 37. 序列化二叉树

题解：

序列化一般采用前序，中序，后序，这里采用前序。

序列化，用前序遍历将二叉树的节点保存到一个字符串中，每个节点之间用’，‘隔开。值得注意的是，在遍历的过程中需要将二叉树看成一颗满二叉树，空节点用’null‘表示。

反序列化，将字符串放在队列que中，用’，‘判断并推入到队列中。通过前序遍历，一边前序遍历一边建立二叉树节点。

代码：

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root==nullptr) return "null,";
        string str=to_string(root->val)+',' ;
        str+=serialize(root->left);
        str+=serialize(root->right);
        return str;   
    }
 
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
  
        queue<string> que;
        string str;
        for(auto i:data){
            if(i==','){
                que.push(str);
                str.clear();
            }
            else
                str.push_back(i);
        }
 
        return rdeserialize(que);
    }
 
    TreeNode* rdeserialize(queue<string> &que){
         if (que.front() == "null") {
            que.pop();
            return nullptr;
        }
 
        TreeNode* root = new TreeNode(stoi(que.front()));
        que.pop();
        root->left = rdeserialize(que);
        root->right = rdeserialize(que);
        return root;
    }
};

结果：

 

剑指 Offer 38. 字符串的排列

题解：

最关键是去重复，因为有重复的字符。可以用一个标志位，判断当前的字符是否出现在前面的字符串中。

代码：

class Solution {
public:
    vector<string> res;
    void dfs(string &s,int sz,int pos){
        if(pos==sz) res.push_back(s);
        for(int i=pos;i<sz;++i){
            bool flag=true;
            for(int j=pos;j<i;++j){
                if(s[j]==s[i]) flag=false;
            } 
            if(flag){
                swap(s[i],s[pos]);
                dfs(s,sz,pos+1);
                swap(s[i],s[pos]);
            }      
        }
    }
    vector<string> permutation(string s) {
        dfs(s,s.size(),0);
        return res;
    }
};

结果：

 

剑指 Offer 39. 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

题解：

方法一：排序

如果重复字符有超过一半的，排序后必然会在数组中间位置。

代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

结果：

 方法二：哈希

用哈希存储，一旦这个值大于数组长度的一半就返回该值。

代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int>map;
        for(auto i:nums){
            ++map[i];
            if(map[i]>nums.size()/2) return i;
        }
        return -1;
    }
};

结果：