第四章 解决问题的思路
面试题27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/
2 7
/ /
1 3 6 9
镜像输出：
4
/
7 2
/ /
9 6 3 1
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
限制：
0 <= 节点个数 <= 1000
/**
* 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==NULL){//树本身为空
return root;
}
if(root->left==NULL && root->right==NULL){//树的左右子树均为空
return root;
}
// 交换根的左右子树
TreeNode* pTemp = root->left;
root->left = root->right;
root->right = pTemp;
//如果左子树不为空，递归交换以左子树为根的左右孙子树
if(root->left){
mirrorTree(root->left);
}
//如果右子树不为空，递归交换以右子树为根的左右孙子树
if(root->right){
mirrorTree(root->right);
}
return root;
}
};
面试题28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
3 3
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
限制：
0 <= 节点个数 <= 1000
/**
* 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 isSymmetric(TreeNode* root) {
return isSymmetric(root,root);
}
bool isSymmetric(TreeNode* pNode1,TreeNode*pNode2){
if(pNode1==NULL && pNode2==NULL){ //如果两个根都为空，自然对称
return true;
}
if(pNode1==NULL || pNode2==NULL){//不是两个根都为空，只有一个为空，那么必然不为空
return false;
}
if(pNode1->val != pNode2->val){ //如果节点的值不相等，肯定不对称
return false;
}
//以上都是递归终止条件，这下面的两行才是真正的递归部分
return isSymmetric(pNode1->left, pNode2->right) && //跟1的左树，与根2的右树比较
isSymmetric(pNode1->right,pNode2->left);//根1的右树，与根2的左树比较
}
};
面试题29. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ret;
int rows = matrix.size();
if(rows<=0) return ret;
int cols = matrix[0].size();
int up = 0, down = rows-1, left = 0, right = cols-1;
while(true){
//从左往右打印，上面那行
for(int i=left;i<=right;++i){
ret.push_back(matrix[up][i]);
}
if(++up>down) break;
//从上往下打印，右边那列
for(int i=up;i<=down;++i){
ret.push_back(matrix[i][right]);
}
if(--right<left) break;
//从右往左打印，下面那行
for(int i=right;i>=left;--i){
ret.push_back(matrix[down][i]);
}
if(--down<up) break;
//从下往上打印，左边那列
for(int i=down;i>=up;--i){
ret.push_back(matrix[i][left]);
}
if(++left>right) break;
}
return ret;
}
};
面试题30. 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示：
各函数的调用总次数不超过 20000 次
class MinStack {
private:
stack<int> stackData;
stack<int> stackMin;
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
stackData.push(x);
if(stackMin.size()==0 || x<stackMin.top()){
stackMin.push(x);
}else{
stackMin.push(stackMin.top());
}
}
void pop() {
assert(stackData.size()>0 && stackMin.size()>0);
stackData.pop();
stackMin.pop();
}
int top() {
assert(stackData.size()>0 && stackMin.size()>0);
return stackData.top();
}
int min() {
assert(stackData.size()>0 && stackMin.size()>0);
return stackMin.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/
面试题31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
bool bPossible = false;
if(pushed.size()>=0 && popped.size()>=0){
auto pushBegin = pushed.begin();
auto pushEnd = pushed.end();
auto popBegin = popped.begin();
auto popEnd = popped.end();
stack<int> stackData;
while(popBegin != popEnd){
while(stackData.empty()||stackData.top()!=*popBegin){
if(pushBegin == pushEnd){
break;
}
stackData.push(*pushBegin);
++pushBegin;
}
if(stackData.top()!=*popBegin){
break;
}
stackData.pop();
++popBegin;
}
if(stackData.empty() && popBegin==popEnd){
bPossible = true;
}
}
return bPossible;
}
};
面试题32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回：
[3,9,20,15,7]
/**
* 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> res;
if(root == NULL){
return res;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* pNode = q.front();
q.pop();
res.push_back(pNode->val);
//变相递归
if(pNode->left){
q.push(pNode->left);
}
if(pNode->right){
q.push(pNode->right);
}
}
return res;
}
};
面试题32 - II. 从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
提示：
节点总数 <= 1000
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//2020.5.17
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;//用于存储最终结果，以便于返回
if(root==NULL){
return res;
}
queue<TreeNode*> q;//队列q用于存储节点指针
q.push(root);//先把根节点放进去
while(!q.empty()){//只要队列不为空，就执行下面的语句
vector<int> resChild;//用于存储每一层的节点值
int len = q.size();//获得队列长度，也就是当前层的所有节点数目
for(int i=0;i<len;++i){//遍历该层的所有节点
TreeNode* pNode = q.front(); //取出队列头节点
resChild.push_back(pNode->val);//把这个节点的值写到resChild
q.pop();//从队列中弹出这个节点指针
//把该结点的左右子树加入到队列中，反正有len约束本次处理的节点个数，只会打印当前层的所有节点，不会打印到下一层
if(pNode->left){
q.push(pNode->left);
}
if(pNode->right){
q.push(pNode->right);
}
}
res.push_back(resChild);//别忘了把子数组加入到大数组
}
return res;
}
};
面试题32 - III. 从上到下打印二叉树 III
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[
[3],
[20,9],
[15,7]
]
提示：
节点总数 <= 1000
/**
* 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>> res;//首先定义一个二维数组
if(root==NULL){
return res;//返回空数组
}
stack<TreeNode*> levels[2];//定义两个栈
int current=0;//当前栈--第一个栈
int next = 1;//当前栈的子树要存入的下一个栈--第二个栈
levels[current].push(root);//把根节点放入第一个栈
while(!levels[0].empty() || !levels[1].empty()){//至少得有一个栈不为空
vector<int> resChild;//定义一个一维的子数组
int len = levels[current].size();//当前栈中的元素个数
for(int i=0;i<len;++i){//遍历当前栈中的每个元素
TreeNode* pNode = levels[current].top();//获得节点指针
levels[current].pop();//把已获得的节点指针弹出栈
resChild.push_back(pNode->val);//把节点值存入子数组
if(current==0){//如果是第1行、第3行、第5行等奇数行，current==0
if(pNode->left){
levels[next].push(pNode->left);//把存在的左子节点存入next栈
}
if(pNode->right){
levels[next].push(pNode->right);//把存在的右子节点存入next栈
}
}
else{//如果是第2行、第4行、第6行等偶数行，current==1，先存右节点，再存左节点
if(pNode->right){
levels[next].push(pNode->right);//把存在的右子节点存入next栈
}
if(pNode->left){
levels[next].push(pNode->left);//把存在的左子节点存入next栈
}
}
}
if(levels[current].empty()){//如果此时current栈为空，说明一行已经遍历结束
res.push_back(resChild);//把子数组添加到大数组
current = 1-current;//更换两个栈的编号，因为永远只处理current栈，把数据存入next栈，第一轮结束后current会从0变成1
next = 1-next;//第一轮结束后next会从1变成0
}
}
return res;
}
};
面试题33. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/
2 6
/
1 3
示例 1：
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
int len = postorder.size();
if(len<0){//这种情况下不由分说，必须false
return false;
}else if(len==0){//当输入的数组为空[]，认为是合法的空二叉搜索树后序遍历结果，因此返回true
return true;
}
return verifyPostorder(postorder,0,postorder.size());//递归调用
}
bool verifyPostorder(vector<int>& postorder,int start,int end) {//end是尾后位置
//这里千万小心，当start>=end时，也就是直到起始位置与尾后位置相遇，竟然一直没有出过错，说明通关成功，应当返回true
if(start>=end){
return true;
}
int root = postorder[end-1];//尾部元素，就是根
//在二叉树中左子树节点的值小于根节点的值，找到第一个大于根节点值的节点，作为左子树的尾后位置
int i=start;//此处务必从start开始，而非从0开始；如果从0开始，那么对于右子树的左孙树会从0开始，这显然不对
for(;i<end-1;++i){
if(postorder[i]>root){
break;
}
}
//在二叉树中右子树节点的值大于根节点的值，找到小于根节点值的右节点表明该序列不是后序遍历序列
int j=i;
for(;j<end-1;++j){
if(postorder[j]<root){
return false;
}
}
bool left = true;
if(i>0){
//cout<<"left-----start="+to_string(start)+" end="+to_string(i)<<endl;
left = verifyPostorder(postorder,start,i);//左子树的起始位置，尾后位置
}
bool right = true;
if(i<end-1){
//cout<<"right-----start="+to_string(i)+" end="+to_string(end-1)<<endl;
right = verifyPostorder(postorder,i,end-1);//右子树的起始位置，尾后位置
}
return (left && right);//左右子树都得符合二叉搜索树要求才行
}
};
如果要求处理一棵二叉树的遍历序列，则可以
（1）先找到二叉树的根节点，
（2）再基于根节点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，
（3）接下来再递归地处理这两个子序列。
面试题34. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
提示：
节点总数 <= 10000
/**
* 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>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> path;
vector<int> pathChild;
if(root==NULL){
return path;
}
int currentSum = 0;
FindPath(root,sum,path,pathChild,currentSum);
return path;
}
void FindPath(TreeNode* root,int sum,vector<vector<int>>& path,vector<int>& pathChild,int currentSum){
currentSum += root->val;//既然遍历到了这个root节点，那就把这个节点的值加上去
pathChild.push_back(root->val);//值都加上去了，这里必然要把节点值存入子路径
bool isLeaf = root->left==NULL && root->right==NULL;//判断是否是叶子节点
if(currentSum==sum && isLeaf){//如果当前总和==要求的总和，同时已经遍历到了叶子节点，说明找到了一条合法路径
path.push_back(pathChild);//把当前合法子路径存入大路径
}
if(root->left){//如果左子树不为空，同样的方法检查一下左子树
FindPath(root->left,sum,path,pathChild,currentSum);
}
if(root->right){//如果右子树不为空，同样的方法检查一下右子树
FindPath(root->right,sum,path,pathChild,currentSum);
}
pathChild.pop_back();//在返回父节点之前，在路径上删除当前节点。如果还需要返回父节点，说明这条路不符合要求，自然要删掉当前路径中的这个节点
}
};
面试题35. 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
Node *p1 = CloneNodes(head);
Node *p2 = ConnectRandomNodes(p1);
return ReconnectNodes(p2);
}
//实现链表节点的复制，从A->B->C->NULL变成A->A'->B->B'>C->C'->NULL
Node* CloneNodes(Node* head){
Node* pNode = head;
while(pNode!=NULL){
// 特别警惕：如下这么写，运行会超时！！！
// Node* pCloned = pNode;//新建节点
// pCloned->val = pNode->val;
// pCloned->next = pNode->next;
// pCloned->random = NULL;
Node* pCloned=new Node(pNode->val);//新建节点pCloned,作为pNode的拷贝，但是，仅拷贝val和next，不拷贝random
pCloned->next = pNode->next;
pNode->next = pCloned;//pNode指向pCloned
pNode = pCloned->next; //pNode指向pCloned的下一个节点
}
return head;
}
//如果原始链表的节点B的random不为空，且指向A，那么节点B'的random应指向A'
Node* ConnectRandomNodes(Node* head){
Node* pNode = head;
while(pNode != NULL){
Node* pCloned = pNode->next;
if(pNode->random!=NULL){
pCloned->random = pNode->random->next;
}
pNode = pCloned->next;
}
return head;
}
//把这两个长链表拆成两个子链表，奇数位置上的为原链表，偶数位置上的为复制出来的链表
Node* ReconnectNodes(Node* head){
Node* pClonedHead = NULL,*pClonedNode = NULL,*pNode = head;
if(pNode!=NULL){
pClonedHead = pNode->next;
pClonedNode = pNode->next;
pNode->next = pClonedNode->next;
pNode = pNode->next;
}
while(pNode!=NULL){
pClonedNode->next = pNode->next;
pClonedNode = pClonedNode->next;
pNode->next= pClonedNode->next;
pNode = pNode->next;
}
return pClonedHead;
}
};
面试题36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
我们希望将二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
提醒：
中序遍历算法的特点是按照从小到大的顺序遍历二叉搜索树的每个节点。
分析：
为了解决这个问题，把树分成3部分：根节点、左子树、右子树。然后把左子树的最大的节点、根节点、右子树中最小的节点连接起来。至于如何把左子树和右子树内部的节点连接成链表，那和原来的问题的实质是一样的，可以递归解决。
普通的中序遍历：
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(root == NULL)
return NULL;
__treeToDoublyList(root);
return NULL;
}
void __treeToDoublyList(Node* root) {
if(root == NULL)
return;
__treeToDoublyList(root -> left);
// do_something
__treeToDoublyList(root -> right);
}
};
本题代码：
/*
// 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* treeToDoublyList(Node* root) {
if(root==NULL) return NULL;//防止root=[]的情况
Node* pLastNodeInList = NULL;
ConvertNode(root,&pLastNodeInList);
//找到头节点，当前的pLastNodeInList指向链表尾结点
Node* head = pLastNodeInList;
while(head!=NULL && head->left!=NULL){
head = head->left;
}
//找到头节点后，将头尾节点连接起来
head->left = pLastNodeInList;
pLastNodeInList->right = head;
//返回头节点
return head;
}
void ConvertNode(Node* pNode,Node** pLastNodeInList){
if(pNode == NULL){//如果为空，返回上一层
return;
}
Node* pCurrent = pNode;//定义一个新的节点pCurrent，避免修改pNode
if(pCurrent->left){//左树不为空
ConvertNode(pCurrent->left,pLastNodeInList);//递归遍历左树
}
//do something
pCurrent->left = *pLastNodeInList;//左边指向*pLastNodeInList,初始为空，后面就不为空了
if(*pLastNodeInList){//当它不为空的时候，让它指向它右边的当前节点
(*pLastNodeInList)->right = pCurrent;
}
*pLastNodeInList = pCurrent;//*pLastNodeInList指向当前节点，相当于右移一个
if(pCurrent->right){//右树不为空
ConvertNode(pCurrent->right,pLastNodeInList);//递归遍历右树
}
}
};
面试题37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：
1
/
2 3
/
4 5
序列化为 "[1,2,3,null,null,4,5]"
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {//序列化，把树序列化为string
ostringstream out;//定义一个输出流
serializeOstream(root, out);//调用序列化函数
return out.str();//返回序列化结果
}
void serializeOstream(TreeNode* root, ostringstream & out){//定义序列化函数
if(root==nullptr){//当树为空的时候，输出"null "返回
out<<"null ";
return;
}
out<<root->val<<" ";//如果root不为空，输出根节点的值后带个空格
serializeOstream(root->left, out);//对左子树做同样的事情
serializeOstream(root->right,out);//对右子树做同样的事情
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {//反序列化，把string反序列化成树
istringstream is(data);//定义一个输入流，并把字符串data与这个流绑定
TreeNode* root = deserializeIstream(is);//调用反序列化函数，将输入流反序列化为树，返回树根
return root;//返回树根
}
TreeNode* deserializeIstream(istringstream & is){//定义反序列化函数
string val;//定义空字符串
is>>val;//把输入流中的内容逐个字符给到这个字符串
if(val=="null"){//如果val等于null
return nullptr;//返回空
}
TreeNode* root = new TreeNode(stoi(val));//根节点
root->left = deserializeIstream(is);//左树
root->right = deserializeIstream(is);//右树
return root;
}
};
面试题38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
解题思路一 回溯算法
* 回溯法
*
* 字符串的排列和数字的排列都属于回溯的经典问题
*
* 回溯算法框架：解决一个问题，实际上就是一个决策树的遍历过程：
* 1. 路径：做出的选择
* 2. 选择列表：当前可以做的选择
* 3. 结束条件：到达决策树底层，无法再做选择的条件
*
* 伪代码：
* result = []
* def backtrack(路径，选择列表):
* if 满足结束条件：
* result.add(路径)
* return
* for 选择 in 选择列表:
* 做选择
* backtrack(路径，选择列表)
* 撤销选择
*
* 核心是for循环中的递归，在递归调用之前“做选择”，
* 在递归调用之后“撤销选择”。
*
* 字符串的排列可以抽象为一棵决策树：
* [ ]
* [a] [b] [c]
* [ab] [ac] [bc] [ba] [ca] [cb]
* [abc] [acb] [bca] [bac] [cab] [cba]
*
* 考虑字符重复情况：
* [ ]
* [a] [a] [c]
* [aa] [ac] [ac] [aa] [ca] [ca]
* [aac] [aca] [aca] [aac] [caa] [caa]
*
* 字符串在做排列时，等于从a字符开始，对决策树进行遍历，
* "a"就是路径，"b""c"是"a"的选择列表，"ab"和"ac"就是做出的选择，
* “结束条件”是遍历到树的底层，此处为选择列表为空。
*
* 本题定义backtrack函数像一个指针，在树上遍历，
* 同时维护每个点的属性，每当走到树的底层，其“路径”就是一个全排列。
* 当字符出现重复，且重复位置不一定时，需要先对字符串进行排序，
* 再对字符串进行“去重”处理，之后按照回溯框架即可。
思路一代码如下：
class Solution {
public:
vector<string> permutation(string s) {
if(s.empty()){
return {};
}
// 对字符串进行排序
sort(s.begin(), s.end());
vector<string> res;
// 标记字符是否遍历过
vector<bool> visit(s.size(), false);
string track;
backtrack(res, s, track, visit);
return res;
}
/*
* 回溯函数
* 使用sort函数对字符串排序，使重复的字符相邻，
* 使用visit数组记录遍历决策树时每个节点的状态，
* 节点未遍历且相邻字符不是重复字符时，
* 则将该字符加入排列字符串中，依次递归遍历。
* */
void backtrack(vector<string> &res, string s, string &track, vector<bool> &visit) {
// 回溯结束条件
if(track.size() == s.size()){
res.push_back(track);
return;
}
// 选择和选择列表
for(int i = 0; i < s.size(); i++){
// 排除不合法的选择
if(visit[i]){
continue;
}
if(i > 0 && !visit[i-1] && s[i-1] == s[i]){
continue;
}
visit[i] = true;
// 做选择
track.push_back(s[i]);
// 进入下一次决策树
backtrack(res, s, track, visit);
// 撤销选择
track.pop_back();
visit[i] = false;
}
}
};
解题思路二 交换法—回溯算法
* 交换法 —— 回溯算法
*
* [a, [b, c]]
* [b, [a, c]] [c, [b, a]]
*
* 如上，对字符串"abc"分割，每次固定一个字符为一部分，
* 其他字符为另一部分，再将固定字符与其他字符进行交换，
* 依次遍历每个字符，再进行回溯递归。
思路二代码如下：
class Solution{
public:
std::vector<std::string> permutation(std::string s) {
// 去重处理
std::set<std::string> res;
backtrack2(s, 0, res);
return std::vector<std::string>(res.begin(), res.end());
}
/*
* 回溯函数
* 使用set函数对字符串字符进行去重，
* 使用swap函数交换两个字符
* */
void backtrack2(std::string s, int start, std::set<std::string> &res) {
// 回溯结束条件
if(start == s.size()){
res.insert(s);
return;
}
for(int i = start; i < s.size(); i++){
// 做选择
std::swap(s[i], s[start]);
// 进入下一次决策树
backtrack2(s, start+1, res);
// 撤销选择
std::swap(s[i], s[start]);
}
}
};