格雷编码（回溯解法）

Problem: 89.格雷编码

基本思路

该问题的解空间为，可看作一棵子集树。当 n = 3 时，对应的子集树分析如下：

根据对子集树的分析，编写回溯算法时可设置标志isRightSubtree 从而确定其结点的左路径是还是。

代码

Java


class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<>();
        dfs(ans, 0, 0, 0, n);
        return ans;
    }
    void dfs(List<Integer> ans, int node, int isRightSubtree, int depth, int n) {
        if (depth == n) {
            ans.add(node);
            return;
        }
        dfs(ans, (node << 1) | isRightSubtree, 0, depth + 1, n);
        dfs(ans, (node << 1) | isRightSubtree ^ 1, 1, depth + 1, n);
    }
}

Python3


class Solution:
    def grayCode(self, n: int):
        ans = []
        self.dfs(ans, 0, 0, 0, n)
        return ans
    def dfs(self, ans: list, node: int, isRightSubtree: int, depth: int, n: int):
        if depth == n:
            ans.append(node)
            return
        self.dfs(ans, (node << 1) | isRightSubtree, 0, depth + 1, n)
        self.dfs(ans, (node << 1) | isRightSubtree ^ 1, 1, depth + 1, n)

TypeScript


var grayCode = (n: number) => {
    const ans: Array<number> = [];
    dfs(ans, 0, 0, 0, n);
    return ans;
}
var dfs = (ans: Array<number>, node: number, isRightSubtree: number, depth: number, n: number) => {
    if (depth == n) {
        ans.push(node);
        return;
    }
    dfs(ans, (node << 1) | isRightSubtree, 0, depth + 1, n);
    dfs(ans, (node << 1) | isRightSubtree ^ 1), 1, depth + 1, n);
}

JavaScript


var grayCode = n => {
    const ans = [];
    dfs(ans, 0, 0, 0, n);
    return ans;
}
var dfs = (ans, node, isRightSubtree, depth, n) => {
    if (depth == n) {
        ans.push(node);
        return;
    }
    dfs(ans, (node << 1) | isRightSubtree, 0, depth + 1, n);
    dfs(ans, (node << 1) | isRightSubtree ^ 1, 1, depth + 1, n);
}


public class Solution {
    public IList<int> GrayCode(int n) {
        IList<int> ans = new List<int>();
        Dfs(ans, 0, 0, 0, n);
        return ans;
    }
    void Dfs(IList<int> ans, int node, int isRightSubtree, int depth, int n) {
        if (depth == n) {
            ans.Add(node);
            return;
        }
        Dfs(ans, (node << 1) | isRightSubtree, 0, depth + 1, n);
        Dfs(ans, (node << 1) | isRightSubtree ^ 1, 1, depth + 1, n);
    }
}


void dfs(int* ans, int* ansSize, int node, int isRightSubtree, int depth, int n) {
    if (depth == n) {
        *(ans + (*ansSize)++) = node;
        return;
    }
    dfs(ans, ansSize, (node << 1) | isRightSubtree, 0, depth + 1, n);
    dfs(ans, ansSize, (node << 1) | !isRightSubtree, 1, depth + 1, n);
}
int* grayCode(int n, int* returnSize) {
    int* ans = (int*) malloc(sizeof(int) * (1 << n));
    *returnSize = 0;
    dfs(ans, returnSize, 0, 0, 0, n);
    return ans;
}

复杂度分析

时间复杂度：。每个深度执行次，树的最大深度为。

空间复杂度：。需要的栈空间为树的最大深度。