89. 格雷编码

这个题其实有个小技巧（个人一直觉得这种所谓的“技巧”其实并不能真正提高编程能力），就是编码的规律。什么规律呢？通过观察我们可以发现，格雷编码是通过上一级的编码得到的。也就是n个数的编码可以通过n - 1个数的编码得到。

如果n = 1，那么编码为[0, 1]；

n = 2，编码为[00, 10, 11, 01]；

n = 3，编码为[000, 100, 110, 010, 011, 111, 101, 001]；

所以，n级的编码的生成，是从n - 1编码的最后一个编码开始倒序遍历，每遍历一个编码，就将这个编码+1后的码字添加到结果列表的后面，然后再将这个编码+0。

比如，n = 2，编码为[00, 10, 11, 01]，倒序遍历，得到：

01，+1后生成新的码字添加到后面，再对01+0，结果列表变成[00, 10, 11, 010, 011]；

接着向前遍历，对11做与上一步相同的处理，结果列表变成[00, 10, 110, 010, 011, 111]；

最后，结果列表变为[000, 100, 110, 010, 011, 111, 101, 001]。这样生成的编码就是符合格雷编码条件的。也就是说，n级格雷编码是由n - 1级格雷编码生成的，这是很典型的递归思想。

最后，把二进制的字符转换成十进制整数就行。代码如下：

class Solution:
    def grayCode(self, n: int) -> List[int]:
        result = []
        if n == 0:
            return [0]
        for i in self.helper(n):
            result.append(int(i, 2))
        return result
 
    def helper(self, n):
        result = []
        if n == 1:
            return ["0", "1"]
        elif n > 1:
            result = self.helper(n - 1)
            index = len(result) - 1
            while index >= 0:
                temp = result[index]
                temp += "1"
                result.append(temp)
                result[index] += "0"
                index -= 1
        return result