PTA 生成格雷码 | C++ | 二叉树

格雷码是一种包含2n个数串的序列，这种序列：

1不存在重复的元素，

2每个元素都是长度为n的二进制数串，

3相邻元素只有一位不同。

例如，长度为23的格雷码为：000，001，011，010，110，111，101，100。

请使用分治法构造格雷码。

提示，使用分治法构造格雷码，详见百度百科。

输入格式:

输入一个正整数n(1<=n<=10)。

输出格式:

输出2n个n位的格雷码。

输入样例:

在这里给出一组输入。例如：

4

输出样例:

在这里给出相应的输出。例如：

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

运用二叉树会得到这样的数字序列： 

 如果加入翻转控制，就可以得到格雷码序列：

#include<bits/stdc++.h>
using namespace std;
int n;
bool flag;
void getGrayCode(string str,int deep,bool flag)
{
    if(deep==n)
    {
        cout<<str<<endl;
        return;
    }
    if (flag==false)
    {
        //若flag为false，左子树添0右子树添1
        getGrayCode(str + "0", deep + 1, false);
        getGrayCode(str + "1", deep + 1, true);
    }
    else{
        //反之
        getGrayCode(str + "1", deep + 1, false);
        getGrayCode(str + "0", deep + 1, true);
    }
}
int main()
{
    cin>>n;
    getGrayCode("",0,false);
}