Strobogrammatic Number II

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return ["11","69","88","96"].

Hint:

1. Try to use recursion and notice that it should recurse with n - 2 instead of n - 1.

Solution: recursion
Space complexity is stack space.

public class Solution {
    public List findStrobogrammatic(int n) {
        return helper(n, n);
    }
    
    public List helper(int remainLen, int n) {
        List res = new ArrayList();
        if (remainLen == 0) {
            return res;
        }
        if (remainLen == 1) {
            res.add("0");
            res.add("1");
            res.add("8");
            return res;
        }
        if (remainLen == 2) {
            if (remainLen != n) {
                res.add("00");  // 00 is invalid
            }
            res.add("11");
            res.add("69");
            res.add("88");
            res.add("96");
            return res;
        }
        
        List sub = helper(remainLen - 2, n);
        for (int i = 0; i < sub.size(); i++) {
            String s = sub.get(i);
            if (remainLen != n) {
                res.add("0" + s + "0");  // 0不能被加到最高位
            }
            res.add("1" + s + "1");
            res.add("6" + s + "9");
            res.add("8" + s + "8");
            res.add("9" + s + "6");
        }
        Collections.sort(res);
        return res;
    }
}

Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

Solution1:

Sorting two arrays take O(nlogn) time. Compare takes O(n) time. Run time complexity is O(nlogn), space complexity is O(n).

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i].start;
            end[i] = intervals[i].end;
        }
        
        Arrays.sort(start);
        Arrays.sort(end);
        
        int activeMeeting = 0;
        int minMeeting = 0;
        int i = 0;
        int j = 0;
        while (i < intervals.length && j < intervals.length) {
            if (start[i] < end[j]) {
                activeMeeting++;
                minMeeting = Math.max(activeMeeting, minMeeting);
                i++;
            } else {
                activeMeeting--;
                j++;
            }
        }
        
        return minMeeting;
    }
}

Solution2: Priority queue, Comparator
Use a priority queue to store the end times. Then we sort the intervals according to its start time. We iterate through the intervals. If the current start time is less than the earliest end time in the pq, numRooms++. Else, remove the earliest time from the pq. For each iteration, we also need to offer the current ending time into the pq.
Reference: http://buttercola.blogspot.com/2015/08/leetcode-meeting-rooms-ii.html

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        
        Arrays.sort(intervals, new IntervalComparator());
        PriorityQueue pq = new PriorityQueue();
        pq.offer(intervals[0].end);
        
        int minRooms = 1;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < pq.peek()) {
                minRooms++;
                pq.offer(intervals[i].end);
            } else {
                pq.poll();
                pq.offer(intervals[i].end);
            }
        }
        
        return minRooms;
    }
    
    public class IntervalComparator implements Comparator {
        @Override
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}

Game of Life

According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up: 

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Solution:
每个细胞有初始状态0(死)和1(活)，先定义一组中间状态，中间状态要求能看出一个细胞变化前后的生死情况。

Run time complexity is O(n ^ 2), constant space.

public class Solution {
    final int dead = 0;
    final int alive = 1;
    
    final int deadToDead = 0;    // 死->死
    final int aliveToAlive = 1;  // 活->活
    final int aliveToDead = 2;   // 活->死
    final int deadToAlive = 3;   // 死->活
    
    public void gameOfLife(int[][] board) {
        if (board == null) {
            return;
        }
        
        int row = board.length;
        int col = board[0].length;
        if (row == 0 || col == 0) {
            return;
        }
        
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                count = 0;
                // 统计周边生命情况
                if (i > 0 && j > 0 && isAliveOld(board[i - 1][j - 1])) {
                    count++;
                }
                if (i > 0 && isAliveOld(board[i - 1][j])) {
                    count++;
                }
                if (i > 0 && j < col - 1 && isAliveOld(board[i - 1][j + 1])) {
                    count++;
                }
                if (j > 0 && isAliveOld(board[i][j - 1])) {
                    count++;
                }
                if (j < col - 1 && isAliveOld(board[i][j + 1])) {
                    count++;
                }
                if (i < row - 1 && j > 0 && isAliveOld(board[i + 1][j - 1])) {
                    count++;
                }
                if (i < row - 1 && isAliveOld(board[i + 1][j])) {
                    count++;
                }
                if (i < row - 1 && j < col - 1 && isAliveOld(board[i + 1][j + 1])) {
                    count++;
                }
                
                // 判断当前细胞生病变化
                if (board[i][j] == alive) {
                    if (count < 2) {
                        // live cell with fewer than 2 live neighbors dies, under-population
                        board[i][j] = aliveToDead;
                    } else if (count == 2 || count == 3) {
                        // live cell with 2 or 3 live neighbors lives on to the next generation
                        board[i][j] = aliveToAlive;
                    } else {  
                        // live cell with more than 3 live neighbors dies, over-population
                        board[i][j] = aliveToDead;
                    }
                } else {
                    if (count == 3) {  
                        // dead cell with exactly 3 live neighbors becomes a live cell, reproduction
                        board[i][j] = deadToAlive;
                    } else {
                        board[i][j] = deadToDead;
                    }
                }
            }
        }
        
        // 根据变化后状态重新赋值
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (isAliveNew(board[i][j])) {
                    board[i][j] = alive;
                } else {
                    board[i][j] = dead;
                }
            }
        }
    }
    
    // 判断某个细胞在变化前是否存活
    public boolean isAliveOld(int cell) {
        if (cell == aliveToAlive || cell == aliveToDead) {
            return true;
        }
        return false;
    }
    
    // 判断某个细胞在变化后是否存活
    public boolean isAliveNew(int cell) {
        if (cell % 2 == 1) {  // 状态1和3
            return true;
        }
        return false;
    }
}

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

Solution: HashMap
Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        String result = "";
        // 处理正负号
        if (numerator > 0 && denominator < 0 || numerator < 0 && denominator > 0) {
            result += "-";
        }
        
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);
        
        // 处理小数点前的位数
        result += num / den;
        if (num % den == 0) {
            return result;
        }
        
        // 如果num % den != 0说明有余数，加上小数点
        result += ".";
        
        num %= den;
        HashMap map = new HashMap();
        num *= 10;
        while (num % den != 0 && !map.containsKey(num)) {
            map.put(num, result.length());
            result += num / den;
            num %= den;
            num *= 10;
        }
        
        if (num % den == 0) {  // fractional part is not repeating
            result += num / den;
            return result;
        } else {
            String str = result.substring(0, map.get(num)) + "(" + result.substring(map.get(num)) + ")";
            return str;
        }
    }
}

Flatten 2D Vector

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].

Hint:

1. How many variables do you need to keep track?
2. Two variables is all you need. Try with x and y.
3. Beware of empty rows. It could be the first few rows.
4. To write correct code, think about the invariant to maintain. What is it?
5. The invariant is x and y must always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it?
6. Not sure? Think about how you would implement hasNext(). Which is more complex?
7. Common logic in two different places should be refactored into a common method.

Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.

Solution:

public class Vector2D {
    List flat;
    int index;
    
    public Vector2D(List> vec2d) {
        index = 0;
        flat = new ArrayList();
        for (int i = 0; i < vec2d.size(); i++) {
            for (int j = 0; j < vec2d.get(i).size(); j++) {
                flat.add(vec2d.get(i).get(j));
            }
        }
    }

    public int next() {
        int val = flat.get(index);
        index++;
        return val;
    }

    public boolean hasNext() {
        return index < flat.size();
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */

Follow Up: using only iterators in C++ or iterators in Java
Reference: http://buttercola.blogspot.com/2015/08/leetcode-flatten-2d-vector.html
Inner iterator must be initilized as Collections.emptyIterator() because the method hasNext() first checks if the innerIterator.hasNext(), so the inner iterator itself must be an iterator at first. 

public class Vector2D {
    Iterator> outer;
    Iterator inner;
    
    public Vector2D(List> vec2d) {
        outer = vec2d.iterator();
        inner = Collections.emptyIterator();  // if outer == null, inner = outer.iterator() will throw exception
    }

    public int next() {
        return inner.next();
    }

    public boolean hasNext() {
        if (inner.hasNext()) {
            return true;
        }
        
        if (!outer.hasNext()) {
            return false;
        }
        
        inner = outer.next().iterator();
        while (!inner.hasNext() && outer.hasNext()) {
            inner = outer.next().iterator();
        }
        return inner.hasNext();
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i = new Vector2D(vec2d);
 * while (i.hasNext()) v[f()] = i.next();
 */

3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

Solution: run time complexity is O(n^3), constant space.

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] < target) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

Follow up: run time complexity is O(n^2), constant space.

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < target) {
                    count = count + right - left;  // 一共有从right->left种情况
                    left++;
                } else {
                    right--;
                }
            }
        }
        return count;
    }
}

Flip Game

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = "++++", after one move, it may become one of the following states:

[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].

Solution: run time complexity is O(n), space complexity is O(n).

public class Solution {
    public List generatePossibleNextMoves(String s) {
        List res = new ArrayList();
        if (s == null || s.length() <= 1) {
            return res;
        }
        
        int i = 0;
        while (i + 1 < s.length()) {
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                StringBuilder sb = new StringBuilder(s);
                sb.setCharAt(i, '-');
                sb.setCharAt(i + 1, '-');
                res.add(sb.toString());
            }
            i++;
        }
        
        return res;
    }
}

Or:

public class Solution {
    public List generatePossibleNextMoves(String s) {
        List res = new ArrayList();
        if (s == null || s.length() <= 1) {
            return res;
        }
        
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.substring(i, i + 2).equals("++")) {
                res.add(s.substring(0, i) + "--" + s.substring(i + 2));
            }
        }
        
        return res;
    }
}

Paint Fence

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

Solution1: dp

Define two DP arrays, diff[n] and same[i].

diff[i] means the number of ways for the fence i which has different color with fence i -1. 

same[i] means the number of ways if fence i has the same color with fence i - 1. 

递推公式：diff[i] = (k - 1) * (same[i - 1] + diff[i - 1])
Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) {
            return 0;
        }
        
        // i - 1 and i - 2 with the same color
        int[] same = new int[n];
        // i - 1 and i - 2 with the different color
        int[] diff = new int[n];
        
        same[0] = 0;
        diff[0] = k;
        
        for (int i = 1; i < n; i++) {
            same[i] = diff[i - 1];
            diff[i] = (k - 1) * (diff[i - 1] + same[i - 1]);
        }
        
        return same[n - 1] + diff[n - 1];
    }
}

Solution2：
Same logic as solution1, but constant space.

public class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) {
            return 0;
        }
        
        int preSame = 0;
        int preDiff = k;
        
        for (int i = 1; i < n; i++) {
            int same = preDiff;
            int diff = (k - 1) * (preDiff + preSame);
            
            preSame = same;
            preDiff = diff;
        }
        
        return preSame + preDiff;
    }
}

Palindrome Permutation

Given a string, determine if a permutation of the string could form a palindrome.

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

Hint:

1. Consider the palindromes of odd vs even length. What difference do you notice?
2. Count the frequency of each character.
3. If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Solution1: HashMap
key存字母， value存字母出现的次数。如果每个字母都出现偶数次，true。如果只有一个字母出现奇数次，true。其余情况返回false。
Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        HashMap map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            }
        }
        
        int oddCount = 0;
        for (Map.Entry entry : map.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                oddCount += 1;
            }
        }
        
        if (oddCount > 1) {
            return false;
        }
        
        return true;
    }
}

Solution2: HashSet
如果set中存在这个字母，从set中将其删除； 如果set中不存在，把字幕放进set里。
loop好之后，查看set的大小，如果大于1，说明有不止1个字母出现奇数次，不可以组成palindrome，返回false。
Run time complexity is O(n), space complexity is O(n).

public class Solution {
    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        HashSet set = new HashSet();
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i))) {
                set.remove(s.charAt(i));
            } else {
                set.add(s.charAt(i));
            }
        }
        
        return set.size() <= 1;
    }
}

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

Solution: binary search
Run time complexity is O(logn), constant space.
注意：初始化 minDiff时候不能等于Integer.MAX_VALUE, 
test case: input[1500000000,1400000000], target -1500000000.0 过不了，因为最小差值超过Integer.MAX_VALUE了已经。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int closestValue(TreeNode root, double target) {
        if (root == null) {
            return 0;
        }
        
        double minDiff = Math.abs(root.val - target);
        int value = root.val;
        while (root != null) {
            if (Math.abs(root.val - target) < minDiff) {
                minDiff = Math.abs(root.val - target);
                value = root.val;
            }
            
            if (root.val < target) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        
        return value;
    }
}

Unique Word Abbreviation

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example: 

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

Solution: run time complexity is O(n), space complexity is O(n).

public class ValidWordAbbr {
    
    HashMap> map = new HashMap>();
    
    public ValidWordAbbr(String[] dictionary) {
        for (String s : dictionary) {
            if (s == null || s.length() == 0) {
                continue;
            }
            
            if (!map.containsKey(getAbbr(s))) {
                ArrayList list = new ArrayList();
                list.add(s);
                map.put(getAbbr(s), list);
            } else {
                if (!map.get(getAbbr(s)).contains(s)) {
                    map.get(getAbbr(s)).add(s);
                }
            }
        }
    }

    public boolean isUnique(String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        
        String key = getAbbr(word);
        if(!map.containsKey(key)) {
            return true;
        } else {
            if (map.get(key).size() == 1 && map.get(key).get(0).equals(word)) {  // dictionary[hello], word="hello" -> unique
                return true;
            }
        }
        return false;
    }
    
    public String getAbbr(String str) {
        if (str.length() <= 2) {
            return str;
        } 
        
        return str.charAt(0) + String.valueOf(str.length() - 2) + str.charAt(str.length() - 1);
    }
}


// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");

Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers "69", "88", and "818" are all strobogrammatic.

Solution1: 逻辑有些乱, run time complexity is O(n), constant space.

public class Solution {
    public boolean isStrobogrammatic(String num) {
        if (num == null || num.length() == 0) {
            return false;
        }
        
        if (isSymmetric(num) && onlyContains(num)) {
            return true;
        }
        
        return false;
    }
    
    public boolean isSymmetric(String num) {
        int l = 0; 
        int r = num.length() - 1;
        while (l < r) {
            if (num.charAt(l) == num.charAt(r) && num.charAt(l) != '6' && num.charAt(l) != '9') {
                l++;
                r--;
            } else {
                if (num.charAt(l) == '6' && num.charAt(r) == '9' || num.charAt(l) == '9' && num.charAt(r) == '6') {
                    l++;
                    r--;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    
    public boolean onlyContains(String num) {
        HashSet set = new HashSet();
        set.add('0');
        set.add('1');
        set.add('6');
        set.add('8');
        set.add('9');
        
        if (num.equals("6") || num.equals("9")) {
            return false;
        }
        
        for (int i = 0; i < num.length(); i++) {
            if(!set.contains(num.charAt(i))) {
                return false;
            }
        }
        
        return true;
    }
}

Solution2: run time complexity is O(n), space complexity is O(n).

public class Solution {
    public boolean isStrobogrammatic(String num) {
        if (num == null || num.length() == 0) {
            return false;
        }
        
        int[] dic = {0,1,-1,-1,-1,-1,9,-1,8,6};
        // int[] dic = new int[10];
        // dic[0] = 0;
        // dic[1] = 1;
        // dic[6] = 9;
        // dic[8] = 8;
        // dic[9] = 6;
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < num.length(); i++) {
            int index = num.charAt(i) - '0';
            sb.insert(0, String.valueOf(dic[index]));
        }
        //sb.reverse();
        return num.equals(sb.toString());
    }
}

Solution3: run time complexity is O(n), constant space.

public class Solution {
    public boolean isStrobogrammatic(String num) {
        if (num == null || num.length() == 0) {
            return false;
        }
        
        int[] dic = new int[10];
        dic[0] = 0;
        dic[1] = 1;
        dic[6] = 9;
        dic[8] = 8;
        dic[9] = 6;
        
        int l = 0;
        int r = num.length() - 1;
        while (l <= r) {
            int indexL = num.charAt(l) - '0';
            int indexR = num.charAt(r) - '0';
            if (indexL != dic[indexR]) {
                return false;
            } else {
                l++;
                r--;
            }
        }
        return true;
    }
}

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        StringBuilder sb = new StringBuilder();
        Queue queue = new LinkedList();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("null,");
            } else {
                sb.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
        }
        
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        } 
        
        String[] vals = data.split(",");
        if (vals[0] == "null") {
            return null;
        }
        
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue queue = new LinkedList();
        queue.add(root);
        
        for (int i = 1; i < vals.length; i = i + 2) {
            TreeNode node = queue.poll();
            if (!vals[i].equals("null")) {
                TreeNode n = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(n);
                node.left = n;
            }
            
            if (!vals[i + 1].equals("null")) {
                TreeNode n = new TreeNode(Integer.parseInt(vals[i + 1]));
                queue.add(n);
                node.right = n;
            }
        }
        
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));