二叉搜索树转化为双向链表
思路：
二叉搜索树的中序遍历就是一个有序序列，对于根节点，当左子树有序之后，把它和左子树的最右节点链接起来。随后遍历右子树，第一个节点是右子树的最左节点，链接起来。
代码：
void ConvertRecursion(TreeNode* root, TreeNode** pLastNode)
{
if (root == NULL)
{
return ;
}
TreeNode* currentNode = root;
if (root->left)
{
ConvertRecursion(root->left, pLastNode);
}
currentNode->left = *pLastNode; //开始链接根和左子树的最后一个节点。
if (*pLastNode)
(*pLastNode)->right = currentNode; //*pLastNode为指针
else
cout << "LastNode is NULL" << endl;
*pLastNode = currentNode; //最后一个指针指向当前节点
if (currentNode->right)
{
ConvertRecursion(root->right, pLastNode);
}
}
TreeNode* TreeConvertToList(TreeNode *root)
{
if (root == NULL)
return NULL;
TreeNode* pLastNode = NULL;
ConvertRecursion(root, &pLastNode); //传递的是指针的地址
TreeNode* p = pLastNode;
while (p&&p->left)
{
p = p->left;
}
return p;
}
字符全排列
思路：
递归思想，当前字符串分为字符和后面的字符串。每次都与后面的字符交换，用begin指针向后移动。当begin到末尾，递归结束。
代码：
void stringallrank1(string s1,int begin)
{
if (begin == s1.size())
cout << s1 << endl;
else
{
for (int i =begin; i < s1.size(); i++)
{
char temp = s1[begin];
s1[begin] = s1[i];
s1[i] = temp;
stringallrank1(s1, begin+1);
//用的是string，递归回来时自动恢复，不用交换回来。
}
}
}
void stringallrank(string s)
{
if (s.empty())
return;
stringallrank1(s,0);
}
八皇后问题
描述：
8X8的棋盘有8个棋子，要求棋子不能同行同列同对角线。求所有摆放个数。
思路：
arr[],下标代表棋子所在行数，值代表棋子所在列数，然后就是全排列问题。用0-7初始化数组，保证不同行同列。所以只用保证不同对角线。
代码：
bool check(int arr[], int len)
{
for (int i = 0; i < len; i++)
{
for (int j = i + 1; j < len; j++)
{
if (j - i == abs(arr[i] - arr[j]))
{
return false;
}
}
}
return true;
}
void Permutation(int arr[], int len, int index,int *num)
{
if (index == len)
{
if (check(arr, len))
{
(*num)++;
/*for (int i = 0; i < len; i++)
{
cout << arr[i];
}
cout << ' ';*/
}
}
for (int i = index; i < len; i++)
{
swap(arr[index], arr[i]);
Permutation(arr, len, index + 1, num);
swap(arr[index], arr[i]); //传入的是数组，递归回来会变
}
}
void eightqueue()
{
int num = 0;
int arr[8];
for (int i = 0; i < 8; i++)
{
arr[i] = i;
}
Permutation(arr, 8, 0, &num);
cout << num;
}