7 搜索與回溯算法

7.1 【BFS】劍指 Offer 32 - I - 從上到下打印二叉樹

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/

??這里借助隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先遍歷，由于需要訪問每一層的節(jié)點(diǎn)，而且這一層訪問才可以訪問下一層，所以可以考慮隊(duì)列的先進(jìn)先出，先把每一層的節(jié)點(diǎn)加入隊(duì)列，然后把這一層的節(jié)點(diǎn)訪問的同時(shí)，也把它們的左右子樹加入隊(duì)列，這樣每一層訪問完之后緊接著就是下一層的節(jié)點(diǎn)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> q;
        if(root!=nullptr) q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode *tmp = q.front();
                q.pop();
                ans.push_back(tmp->val);
                if(tmp->left!=nullptr) q.push(tmp->left);
                if(tmp->right!=nullptr) q.push(tmp->right); 
            }
        }
        return ans;
    }
};

7.2【BFS】劍指 Offer 32 - II - 從上到下打印二叉樹 II

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/

??這里借助隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先遍歷，由于需要訪問每一層的節(jié)點(diǎn)，而且這一層訪問才可以訪問下一層，所以可以考慮隊(duì)列的先進(jìn)先出，先把每一層的節(jié)點(diǎn)加入隊(duì)列，然后把這一層的節(jié)點(diǎn)訪問的同時(shí)，也把它們的左右子樹加入隊(duì)列，這樣每一層訪問完之后緊接著就是下一層的節(jié)點(diǎn)。以上一題不同的是每層的數(shù)要存放為一個(gè)向量，最后返回多個(gè)向量。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        if(root!=nullptr) q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i=0;i<n;i++)
            {
                TreeNode *node = q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left!=nullptr) q.push(node->left);
                if(node->right!=nullptr) q.push(node->right); 
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

7.3 【BFS】【雙端隊(duì)列】劍指 Offer 32 - III - 從上到下打印二叉樹 III

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/

??這里借助雙端隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先遍歷，由于需要訪問每一層的節(jié)點(diǎn)，而且這一層訪問才可以訪問下一層，對(duì)于奇數(shù)層來說，訪問的順序是從左到右，而偶數(shù)層是從右到左，所以可以做如下操作：

• 奇數(shù)層：從左往右取隊(duì)列元素，但是每個(gè)元素先取其左子樹再取右子樹，然后從隊(duì)列末尾插入；
• 偶數(shù)層：從右往左取隊(duì)列元素，但是每個(gè)元素先取其右子樹再取左子樹，然后從隊(duì)列頭部插入。

??這樣就可以保證每一層的順序連在一起時(shí)之字形順序了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        deque<TreeNode*> q;
        if(root!=nullptr) q.push_back(root);
        bool flag = true;
        while(!q.empty())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i=0;i<n;i++)
            {
                TreeNode *node;
                if(flag)
                {
                    node = q.front();
                    q.pop_front();
                    if(node->left!=nullptr) q.push_back(node->left);
                    if(node->right!=nullptr) q.push_back(node->right);
                }
                else
                {
                    node = q.back();
                    q.pop_back();
                    if(node->right!=nullptr) q.push_front(node->right);
                    if(node->left!=nullptr) q.push_front(node->left);
                }
                tmp.push_back(node->val);
            }
            flag = !flag;
            ans.push_back(tmp);
        }
        return ans;
    }
};

7.4 【BFS】劍指 Offer 26 - 樹的子結(jié)構(gòu)

https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/

??這里把A的每個(gè)結(jié)點(diǎn)與B進(jìn)行比較，如果結(jié)點(diǎn)相同則看它們的左右子樹是否相同即可，這里借助自定義函數(shù)來判斷A和B是否為包含關(guān)系，也就是A包含B，函數(shù)定義如下：

• 如果B為空，說明此時(shí)B的所有結(jié)點(diǎn)遍歷完了，B為A的子樹；
• 如果B不為空A為空，說明此時(shí)A的所有結(jié)點(diǎn)遍歷完了但是B還有結(jié)點(diǎn)，則B不是A的子樹；
• 如果此時(shí)A和B的結(jié)點(diǎn)相同，還要判斷它們的左右子樹是否相同。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool is_contain(TreeNode* A, TreeNode* B) {
        if(B==nullptr) return true;
        if(A==nullptr) return false;

        if(A->val==B->val) return is_contain(A->left,B->left) && is_contain(A->right,B->right);
        else return false;
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(A==nullptr || B==nullptr) return false;

        if(A->val==B->val && is_contain(A,B)) return true;
        else return isSubStructure(A->left,B) || isSubStructure(A->right,B);
    }
};

7.5 【遞歸】劍指 Offer 27 - 二叉樹的鏡像

https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/

??直接交換每個(gè)結(jié)點(diǎn)的左右子樹，然后遞歸返回即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==nullptr) return nullptr;
        swap(root->left,root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

7.6 【遞歸】【雙指針】劍指 Offer 28 - 對(duì)稱的二叉樹

https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/

??利用雙指針分別從樹的左右子樹往下判斷是否對(duì)稱，這里需要注意的是雙指針最后必須同時(shí)為空才行，如果有一個(gè)先為空說明這棵二叉樹是不對(duì)稱的，同時(shí)雙指針也要對(duì)稱著向下移動(dòng)，比如l左移r右移、l右移r左移。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* l, TreeNode* r) {
        if(l==nullptr && r==nullptr) return true;
        if(l==nullptr || r==nullptr) return false;
        return l->val==r->val && check(l->left,r->right) && check(l->right,r->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }
};

7.7 【DFS】【回溯】【剪枝】劍指 Offer 12 - 矩陣中的路徑

https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/

??這里我們首先找到矩陣中和字符串的第一個(gè)字符對(duì)應(yīng)的位置，然后從這個(gè)位置開始分別向上下左右深度搜索，直到找到與字符串完成對(duì)應(yīng)的一條搜索路徑即可，但是這里需要設(shè)置一些剪枝規(guī)則提前終止不必要的搜索：

• 如果訪問越界了，需要提前終止搜索；
• 如果當(dāng)前在矩陣中訪問到的字符與目前在字符串中遍歷到的字符不一樣，需要提前終止搜索。

??這里為了防止矩陣中的元素被重復(fù)使用，訪問過的元素統(tǒng)一賦值為空，當(dāng)這一輪搜索結(jié)束之后再用字符串賦值回去，避免影響判斷。

class Solution {
private:
    int row,col;
public:
    bool exist(vector<vector<char>>& board, string word) {
        row = board.size();
        col = board[0].size();
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
        //矩陣訪問越界and當(dāng)前訪問字符不一致時(shí)，需要提前終止搜索，返回false
        if(i>=row || i<0 || j>=col || j<0 || board[i][j]!=word[k]) return false;
        //字符串遍歷到最后一個(gè)字符，說明找到了一條路徑，返回true
        if(k==word.size()-1) return true;
        //避免矩陣重復(fù)訪問，已訪問的賦值為空
        board[i][j] = ' ';
        //上下左右深度搜索
        bool flag = dfs(board,word,i-1,j,k+1) || dfs(board,word,i+1,j,k+1) || 
                    dfs(board,word,i,j-1,k+1) || dfs(board,word,i,j+1,k+1);
        //此輪搜索結(jié)束，已訪問過的再賦值回去
        board[i][j] = word[k];
        return flag;
    }
};

7.8 【DFS】劍指 Offer 13 - 機(jī)器人的運(yùn)動(dòng)范圍

https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

??利用DFS解題，雖然機(jī)器人可以上下左右移動(dòng)，但是最后算的是機(jī)器人可以到達(dá)多少個(gè)格子，所以可以把上下左右簡(jiǎn)化為下和右兩個(gè)行動(dòng)，并且設(shè)置一個(gè)數(shù)組visit來記錄每個(gè)格子是否被訪問過。這道題的難點(diǎn)在于行坐標(biāo)和列坐標(biāo)的位數(shù)之和如何快速計(jì)算，這里我們可以發(fā)現(xiàn)一個(gè)規(guī)律，假設(shè)坐標(biāo)為18,19,20,21,22時(shí)，數(shù)位和分別為9,10,2,3,4，這里如果坐標(biāo)不是10的倍數(shù)，那么數(shù)位和隨著坐標(biāo)數(shù)的增加依次加1，而當(dāng)來到20時(shí)，數(shù)位和直接變成了2，比19的數(shù)位和少8，同理坐標(biāo)29,30,31的數(shù)位和分別是11,3,4，所以可以總結(jié)出這樣的規(guī)律：

• 如果坐標(biāo)不是10的倍數(shù)，數(shù)位和較之前的坐標(biāo)加1；
• 如果坐標(biāo)是10的倍數(shù)。數(shù)位和較之前的坐標(biāo)減8.

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visit(m,vector<bool>(n,false));
        return dfs(0,0,0,0,visit,m,n,k);
    }

    int dfs(int i, int j, int si, int sj, vector<vector<bool>> &visit, int m, int n, int k) {
        if(i<0 || i>=m || j<0 || j>=n || si+sj>k || visit[i][j]) return 0;
        visit[i][j] = true;
        int new_si = (i+1)%10 != 0 ? si+1 : si-8;
        int new_sj = (j+1)%10 != 0 ? sj+1 : sj-8;
        return 1 + dfs(i,j+1,si,new_sj,visit,m,n,k) + dfs(i+1,j,new_si,sj,visit,m,n,k);
    }
};

7.9 【DFS】【遞歸】劍指 Offer 34 - 二叉樹中和為某一值的路徑

https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

??利用DFS解題，順著根結(jié)點(diǎn)先往一個(gè)子結(jié)點(diǎn)方向遍歷，然后再去遍歷另一個(gè)，這里的難點(diǎn)在于精準(zhǔn)判斷是否達(dá)到目標(biāo)和，一共需要以下幾個(gè)條件：

• 截止目前的路徑上的val之和等于target；
• 目前結(jié)點(diǎn)是葉子結(jié)點(diǎn)，也就是該結(jié)點(diǎn)的左右結(jié)點(diǎn)都為空。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        vector<int> path;
        dfs(root,target,path);
        return ans;
    }

    void dfs(TreeNode* root, int target, vector<int> path) {
        if(root==nullptr) return;
        path.push_back(root->val);
        if(root->val==target && root->left==nullptr && root->right==nullptr)
        {
            ans.push_back(path);
            return;
        }
        dfs(root->left,target-root->val,path);
        dfs(root->right,target-root->val,path);
    }
};

7.10 【DFS】【遞歸】【雙指針】劍指 Offer 36 - 二叉搜索樹與雙向鏈表

https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

??這道題其實(shí)就是把給出的這個(gè)二叉樹變成中序遍歷的結(jié)果輸出，然后在中序遍歷的過程中改變左右子樹的指向即可，使之變成雙向循環(huán)鏈表，這里借助雙指針來構(gòu)造循環(huán)鏈表，head指向循環(huán)鏈表的開始，pre指向中序遍歷過程中訪問到的每個(gè)結(jié)點(diǎn)的前序結(jié)點(diǎn)，按照中序遍歷的過程進(jìn)行DFS，遍歷到最下面的左子樹時(shí)，開始構(gòu)造鏈表，此時(shí)左子樹應(yīng)該是當(dāng)前root的前驅(qū)，這樣就構(gòu)造出了一個(gè)循環(huán)，然后依次往上返回構(gòu)造其他循環(huán)，最后要把頭尾連接起來。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node *head=nullptr, *pre=nullptr;

    Node* treeToDoublyList(Node* root) {
        if(root==nullptr) return root;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }

    void dfs(Node* root) {
        if(root==nullptr) return;
        dfs(root->left);
        if(pre!=nullptr) pre->right = root;
        else head = root;
        root->left = pre;
        pre = root;
        dfs(root->right);
    }
};

7.11 【DFS】劍指 Offer 54 - 二叉搜索樹的第k大節(jié)點(diǎn)

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

??這道題是找第k大的結(jié)點(diǎn)，二叉搜索樹的中序遍歷結(jié)果是從小到大排序，所以其實(shí)就是對(duì)二叉搜索樹進(jìn)行倒過來的中序遍歷，每遍歷一個(gè)元素k–，當(dāng)k為0時(shí)就是最終結(jié)果。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    int kthLargest(TreeNode* root, int k) {
        dfs(root,k);
        return ans;
    }

    void dfs(TreeNode* root,int &k) {
        if(root==nullptr) return;
        dfs(root->right,k);
        k--;
        if(k==0) ans = root->val;
        dfs(root->left,k);
    }
};

7.12 【DFS】劍指 Offer 55 - I - 二叉樹的深度

https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/

??考察深度優(yōu)先遍歷，從上往下深度搜索，沒找到一個(gè)節(jié)點(diǎn)就把當(dāng)前的深度dpt加1，最后取最大的那個(gè)dpt即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int depth = 1;
    int maxDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        dfs(root,0);
        return depth;
    }
    
    void dfs(TreeNode* root, int dpt) {
        if(root==nullptr)
        {
            depth = max(depth,dpt);
            return;
        }
        dpt++;
        dfs(root->left,dpt);
        dfs(root->right,dpt);
    }
};

7.13 【DFS】劍指 Offer 55 - II - 平衡二叉樹

https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/

??采用自底向上的方法，首先判斷最下面的節(jié)點(diǎn)是否滿足平衡二叉樹的條件，不滿足就把當(dāng)前高度賦值為-1，這樣一步步從下往上遞增，最后只需看根結(jié)點(diǎn)的高度是多少即可，如果采用自頂向下的話則會(huì)存在某些節(jié)點(diǎn)多次計(jì)算高度，會(huì)增加時(shí)間復(fù)雜度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(depth(root)!=-1) return true;
        else return false;
    }

    int depth(TreeNode* root) {
        if(root==nullptr) return 0;
        int left_depth = depth(root->left);
        int right_depth = depth(root->right);
        if(left_depth == -1 || right_depth == -1 || abs(left_depth - right_depth) > 1)
        {
            return -1;
        }
        else return max(left_depth,right_depth) + 1;
    }
};

7.14 【位運(yùn)算】劍指 Offer 64 - 求1+2+…+n

https://leetcode.cn/problems/qiu-12n-lcof/

??求和公式為sum=n*(n+1)/2，這里為什么用bool呢，其實(shí)用char也行，因?yàn)樗鼈兌颊加靡粋€(gè)字節(jié)，意思就是構(gòu)造了一個(gè)n*(n+1)的數(shù)組，然后先計(jì)算這個(gè)數(shù)組一共多少字節(jié)，對(duì)于除2操作直接位運(yùn)算就行了。

class Solution {
public:
    int sumNums(int n) {
        bool ans[n][n+1];
        return sizeof(ans)>>1;
    }
};

7.15 【DFS】【遞歸】劍指 Offer 68 - I - 二叉搜索樹的最近公共祖先

https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

??這道題需要明白一點(diǎn)，就是x的值一定是在p和q之間的，所以在深度遍歷時(shí)只需比較當(dāng)前根節(jié)點(diǎn)的值和p、q的值的大小即可，如果當(dāng)前節(jié)點(diǎn)的值比p和q都大，說明最近公共祖先在左子樹，如果當(dāng)前節(jié)點(diǎn)的值比p和q都小，說明最近公共祖先在右子樹，如果都不滿足說明目前找到的就是最近公共祖先了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if(root->val > p->val && root->val > q->val)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        else if(root->val < p->val && root->val < q->val)
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        else return root;
    }
};

7.16 【DFS】劍指 Offer 68 - II - 二叉樹的最近公共祖先

https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

??這題為一般二叉樹中找最近公共祖先，首先要明確公共祖先的判斷標(biāo)準(zhǔn)，共有以下三點(diǎn)：

• (1)p和q在二叉樹兩側(cè)（也就是一個(gè)在左子樹一個(gè)在右子樹），則找最近的root結(jié)點(diǎn)；
• (2)p和q在二叉樹同側(cè)（也就是同在左子樹或者右子樹），則找p或者q；

??下面定義雙指針left和right來判斷目前節(jié)點(diǎn)的左右子樹中是否有p和q，并給出以下判斷標(biāo)準(zhǔn)：

• (1)如果left和right均不為空，說明p和q一個(gè)在左子樹一個(gè)在右子樹，返回當(dāng)前root節(jié)點(diǎn)；
• (2)如果left為空，right不為空，說明p和q都在右子樹中，返回right；
• (3)如果left不為空，right為空，說明p和q都在左子樹中，返回left。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr || root==p || root==q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left==nullptr) return right;
        if(right==nullptr) return left;
        return root;
    }
};

7.17 【DFS】【模擬】劍指 Offer 37 - 序列化二叉樹

https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/

??本題主要實(shí)現(xiàn)兩個(gè)功能，分別是二叉樹的序列化和反序列化，也就是給定字符串變成二叉樹，或者給定二叉樹變成字符串，下面分開來介紹實(shí)現(xiàn)思路：
（1）二叉樹->字符串
??這個(gè)其實(shí)就是對(duì)二叉樹進(jìn)行中序遍歷即可，然后把每個(gè)節(jié)點(diǎn)的值保存到字符串中，難點(diǎn)在于如何把整數(shù)轉(zhuǎn)變成字符串，因?yàn)檫@里的數(shù)值可能是多位數(shù)或者負(fù)數(shù)，所以這里定義了一個(gè)函數(shù)int_to_str()來實(shí)現(xiàn)將整數(shù)轉(zhuǎn)變?yōu)樽址?，同時(shí)在函數(shù)tree_to_str()中實(shí)現(xiàn)將二叉樹轉(zhuǎn)為字符串，這里注意每個(gè)數(shù)值后面要加上逗號(hào)’,‘。
（2）字符串->二叉樹
??這個(gè)就比較難了，首先要把字符串中的字符轉(zhuǎn)為數(shù)字，這里通過自定義函數(shù)str_to_int()來實(shí)現(xiàn)，接下來就是為每一個(gè)生成的數(shù)值構(gòu)造一個(gè)節(jié)點(diǎn)，按照中序遍歷的情況依次構(gòu)造二叉樹，當(dāng)上述準(zhǔn)備工作完成之后，下面就是要對(duì)給定的字符串進(jìn)行切割，分割標(biāo)準(zhǔn)為逗號(hào)’,'，遍歷是每遇到逗號(hào)說明是一個(gè)節(jié)點(diǎn)，然后把這個(gè)節(jié)點(diǎn)通過上述兩步操作插入到二叉樹中即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
        string int_to_str(int num) {
        bool flag = true;
        string ans;
        if(num < 0)
        {
            num = -num;
            flag = false;
        }
        while(num)
        {
            ans.insert(ans.begin(), num % 10 + '0');
            num /= 10;
        }
        if(flag==false) ans.insert(ans.begin(),'-');
        return ans;
    }

    int str_to_int(string s) {
        int idx = 0;
        bool flag = true;
        int ans = 0;
        if(s[idx]=='-')
        {
            flag = false;
            idx++;
        }
        while(idx < s.size())
        {
            ans = s[idx] - '0' + ans * 10;
            idx++;
        }
        if(flag==false) ans = -ans;
        return ans;
    }

    void tree_to_str(TreeNode* root, string& str) {
        if(root==nullptr)
        {
            str += "/,";
            return;
        }
        str += int_to_str(root->val);
        str += ",";
        tree_to_str(root->left, str);
        tree_to_str(root->right, str);
    }

    TreeNode* str_to_tree(vector<string>& s, int& idx) {
        if(s[idx]=="/") return nullptr;
        int val = str_to_int(s[idx]);
        TreeNode* root = new TreeNode(val);
        root->left = str_to_tree(s, ++idx);
        root->right = str_to_tree(s, ++idx);
        return root;
    }

public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans;
        tree_to_str(root,ans);
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> s;
        int idx = 0;
        while(idx < data.size())
        {
            int tmp = idx;
            while(data[idx]!=',') idx++;
            string now = data.substr(tmp, idx - tmp);
            s.push_back(now);
            idx++;
        }
        idx = 0;
        TreeNode* root = str_to_tree(s, idx);
        return root;
    }
};

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

7.18 【DFS】【回溯】【模擬】劍指 Offer 38 - 字符串的排列

https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/

??這題難點(diǎn)在于如何保證字符不重復(fù)遍歷，同時(shí)也要保證最后得到的字符串里面沒有重復(fù)的字符串，這里考慮到可能原始的字符串里會(huì)有一些重復(fù)字符，所以先對(duì)原始的字符串進(jìn)行排序，然后定義一個(gè)數(shù)組visited來保存每一位是否被訪問過，而在深度遍歷的時(shí)候，對(duì)于每次訪問的字符，也要判斷它是否為重復(fù)的字符，防止重復(fù)的字符被多次訪問，但最后其實(shí)都是得到的同一個(gè)字符串，最后本次遍歷完之后還要把臨時(shí)字符串tmp和visited置回原來的狀態(tài)。文章來源地址http://www.zghlxwxcb.cn/news/detail-547195.html

class Solution {
public:
    vector<string> ans;
    vector<int> visited;

    void dfs(string &s, int i, int length, string &tmp) {
        if(i==length)
        {
            ans.push_back(tmp);
            return;
        }

        for(int j=0;j<length;j++)
        {
            if(visited[j] || (j>0 && !visited[j-1] && s[j-1]==s[j])) continue;

            visited[j] = 1;
            tmp.push_back(s[j]);

            dfs(s,i+1,length,tmp);
            tmp.pop_back();
            visited[j] = 0;
        }
    }

    vector<string> permutation(string s) {
        int length = s.size();
        visited.resize(length);
        string tmp;

        sort(s.begin(),s.end());
        dfs(s,0,length,tmp);

        return ans;
    }
};

到了這里，關(guān)于【leetcode刷題之路】劍指Offer（3）——搜索與回溯算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！