Solution using binary tree.

• We can represent binary numbers as paths of binary tree.
Left node value is parent value times 2.
Right node value is parent value times 2 plus 1.
We can only change a single part of a path at a time.
We will look for a pattern to accomplish this.

``````     /*
*                                  _____0_____                     000                      0000
*                                 /           \                    001                      0001
*                              __0_           _1__                 011                      0011
*                             /    \         /    \                010                      0010
*                            0      1       2      3               110                      0110
*                           / \    / \     / \    / \              111                      0111
*                          0   1  2   3   4   5  6   7             101                      0101
*                                                                  100                      0100
*              n=0                                  0                                       1100
*              n=1                    0                            1                        1101
*              n=2             0            1              3                2               1111
*              n=3         0      1     3       2       6     7         5       4           1110
*              n=4        0,1    3,2   6,7     5,4    12,13 15,14      10,11   9,8          1010
*                                                                                           1011
*                                                                                           1001
*                                                                                           1000
*/
public class Solution {
public List<Integer> grayCode(int n){
List<Integer> result = new ArrayList<Integer>();
result.add(0);

for (int i=0;i<n;i++){
boolean smallerFirst=true;
List<Integer> temp = new ArrayList<Integer>();
for (int val:result){
if (smallerFirst){
temp.add(val*2);
temp.add(val*2+1);
}
else{
temp.add(val*2+1);
temp.add(val*2);
}
smallerFirst=!smallerFirst;
}
result = temp;
}
return result;
}
}``````

• I came up with even simpler binary tree solution

``````public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> grayList = new ArrayList<Integer>();
buildGrayTree(0, n--, grayList, false);
return grayList;
}

private void buildGrayTree(int parentVal, int level, List<Integer> grayList, boolean reverse){
if (level == 0){
grayList.add(parentVal);
return;
}
if(reverse){
buildGrayTree(parentVal*2+1, level-1, grayList, false);
buildGrayTree(parentVal*2, level-1, grayList, true);
}
else{
buildGrayTree(parentVal*2, level-1, grayList, false);
buildGrayTree(parentVal*2+1, level-1, grayList, true);
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.