Solution using binary tree.


  • 3
    Q

    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;
    	}
    }

  • 0
    Q

    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);
            }
        }
    }

Log in to reply
 

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