Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3




But the following is not:
    1
   / \
  2   2
   \   \
   3    3




Note:
Bonus points if you could solve it both recursively and iteratively.


confused what "{1,#,2,3}" means?
Solution1: recursion

Run time complexity is O(n), space complexity is stack space O(logn).

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) 
            return true;
        
        return helper(root.left, root.right);
    }
    
    public boolean helper(TreeNode left, TreeNode right) {
        if(left == null && right == null)
            return true;
        if(left == null || right == null)
            return false;
        if(left.val != right.val)
            return false;
        return helper(left.right, right.left) && helper(left.left, right.right);
    }
}

Solution2: iterative
用两个queue来保存左右节点，一层一层遍历。

Run time complexity is O(n), space complexity is O(n).

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) 
            return true;
        if(root.left == null && root.right == null)
            return true;
        if(root.left == null || root.right == null)
            return false;
        
        LinkedList queue1 = new LinkedList();
        LinkedList queue2 = new LinkedList();
        queue1.add(root.left);
        queue2.add(root.right);
        while(!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode curL = queue1.poll();
            TreeNode curR = queue2.poll();
            if(curL.left == null && curR.right != null || curL.left != null && curR.right == null)
                return false;
            if(curL.right == null && curR.left != null || curL.right != null && curR.left == null)
                return false;
            if(curL.val != curR.val)
                return false;
            
            if(curL.left != null && curR.right != null) {
                queue1.add(curL.left);
                queue2.add(curR.right);
            }
            if(curL.right != null && curR.left != null) {
                queue1.add(curL.right);
                queue2.add(curR.left);
            }
        }
        return true;
    }
}

Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Solution1: recursion

如果两个结点都是null，返回true。

如果其中一个是null，说明在一棵树上结点到头，另一棵树结点还没结束，即树不相同，或者两个结点都非空，并且结点值不相同，返回false。

递归处理两个结点的左右子树，返回左右子树递归的与结果即可。

先序遍历，时间复杂度是O(n)，空间复杂度是O(logn)。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        
        if(p == null || q == null)
            return false;
        
        if(p.val != q.val)
            return false;
            
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/22839819
Solution2: iterative

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        
        LinkedList q1 = new LinkedList();
        LinkedList q2 = new LinkedList();
        
        q1.offer(p);
        q2.offer(q);
        
        while(!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode pNode = q1.poll();
            TreeNode qNode = q2.poll();
            
            if(pNode == null) {
                if(qNode != null)
                    return false;
                else 
                    continue;
            }
            
            if(qNode == null || qNode.val != pNode.val) {
                return false;
            }
            
            q1.offer(pNode.left);
            q1.offer(pNode.right);
            q2.offer(qNode.left);
            q2.offer(qNode.right);
        }
        return true;
    }
}

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

Given 1->1->2, return 1->2.

Given 1->1->2->3->3, return 1->2->3.

Solution:

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
            return null;
        if(head.next == null)
            return head;
        
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null) {
            if(cur.val == pre.val) {
                pre.next = cur.next;
            }else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }
}

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Solution:

从最后一位开始，对每一位进行加一，然后判断进位，如果有进位就继续到下一位，否则就可以返回了。

如果到了最高位进位仍然存在，重新new一个数组，把第一个为赋成1（因为只是加一操作，其余位一定是0，否则不会进最高位）。
一次扫描，所以算法复杂度是O(n)，n是数组的长度。而空间上，一般情况是O(1)，但是如果数是全9，那么是最坏情况，需要O(n)的额外空间。

public class Solution {
    public int[] plusOne(int[] digits) {
        if(digits == null || digits.length == 0)
            return null;
        
        for(int i = digits.length - 1; i >= 0; i--) {
            if(digits[i] + 1 == 10) {
                digits[i] = 0;
            }else {
                digits[i] = digits[i] + 1;
                return digits;
            }
        }
        
        //deal with the carry of the first number
        int[] res = new int[digits.length + 1];
        res[0] = 1;  
        //no need to copy the rest elements in digits, 
        //because when we have carry at the first number, 
        //this means that rest numbers in digits are already 0 now.
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/22365957

Follow up: Plus one，输入输出都是int，不能用＋和－

Bit operator
&: 都是1， ＝1
|: 有1， ＝ 1
^: 相同＝0， 不同＝1
~: 0->1, 1->0

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

Solution:

One pointer points to the end of string, then loop from right to left.

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

public class Solution {
    public int lengthOfLastWord(String s) {
        if(s == null || s.length() == 0)
            return 0;
        
        s = s.trim();  //get rid of space at beginning and end
        int count = 0;
        for(int i = s.length() - 1; i >= 0; i--) {
            if(s.charAt(i) != ' ') {
                count++;
            }else {
                return count;
            }
        }
        return count;
    }
}

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Solution1: two pointers 不考虑顺序
两个指针left和right，left指第一个element，right指最后一个element。
如果A[right] == elem，直接跳过。
然后如果A[left] == elem，将right所指的element复制给left，left++, right--。

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

public class Solution {
    public int removeElement(int[] A, int elem) {
        if(A == null || A.length == 0)
            return 0;
        
        int l = 0, r = A.length - 1;
        while(l <= r) {
            if(A[r] == elem) {
                r--;
                continue;
            }
            
            if(A[l] == elem) {
                A[l] = A[r];
                l++;
                r--;
            }else {
                l++;
            }
        }
        
        return r + 1;
    }
}

Solution2：仍然保持顺序

public class Solution {
    public int removeElement(int[] A, int elem) {
        if(A == null || A.length == 0)
            return 0;
        
        int p1 = 0, p2 = 0;
        while(p2 < A.length) {
            if(A[p2] == elem) {
                p2++;
            }else {
                A[p1] = A[p2];
                p1++;
                p2++;
            }
        }
        
        return p1;
    }
}

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,

Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

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

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A == null || A.length == 0) {
            return 0;
        }
        
        int p1 = 0, p2 = 0;
        while(p2 < A.length) {
            if(A[p1] == A[p2]) {
                p2++;
            }else {
                p1++;
                A[p1] = A[p2];
                p2++;
            }
        }
        
        return p1 + 1;
    }
}