Invert a binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Solution:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        TreeNode* temp = NULL;
        if ((root == NULL))
            return root;
        temp = root -> left;
        root -> left = invertTree(root -> right);
        root -> right = invertTree(temp);
        return root;
    }
    // Iterative
    // BFS with queue.
};

Power of Two

Given an integer, write a function to determine if it is a power of two.

Solution:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        /*
        if (n == 0)
            return false;
        else if (n == 1)
            return true;
        else if (n % 2 == 0)
            return isPowerOfTwo(n/2);
        else
            return false;
        */
        // Iterative.
        /*
        while (n > 1) {
            if (n % 2 != 0) {
                return false;
            }
            n /= 2;
        }
        return n == 1;
        */
       
        // Bitwise.
        if (n > 0 && !(n & (n - 1))) {
            return true;
        }
        return false;
    }
};

Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution:

class Queue {
private:
    stack<int> st, tmp;
public:
    // Push element x to the back of queue.
    void push(int x) {
        st.push(x);
    }

    // Removes the element from in front of queue.
    void pop(void) {
        if (tmp.empty()) {
            while (!st.empty()) {
                tmp.push(st.top());
                st.pop();
            }
        }
        tmp.pop();
    }

    // Get the front element.
    int peek(void) {
      if (tmp.empty() && !st.empty()) {
            while (!st.empty()) {
                tmp.push(st.top());
                st.pop();
            }
        }
        return tmp.top();
    }

    // Return whether the queue is empty.
    bool empty(void) {
        if (st.empty() && tmp.empty())
            return true;
        return false;
    }
};

Palindrome Linked lists

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

Solution:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* temp = head;
        stack<int> st;
        while (temp != NULL) {
            st.push(temp->val);
            temp = temp -> next;
        }
     
        while (!st.empty()) {
            if (st.top() != head -> val) {
                return false;
            } else {
                st.pop();
                head = head -> next;
            }
        }
        return true;
    }
    // For o(1) space,
    // 1. Find pointer to center node.
    // 2. Reverse the link list from center node.
    // Finally compare.
};

======== o(1) =======

 ListNode * reverse(ListNode *head) {
        ListNode *cur = head, *pre = NULL, *next = NULL;
       
        while (cur != NULL) {
            next = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        ListNode *trav = head, *center = head;
       
        if (head == NULL || head -> next == NULL) {
            return true;
        }
       
        while (trav != NULL) {
            if (trav -> next != NULL) {
                trav = trav -> next -> next;
                center = center -> next;
            } else {
                trav = NULL;
            }
        }
       
        ListNode *end = reverse(center);
       
        while (end != NULL) {
            if (head -> val != end -> val) {
                return false;
            }
            head = head -> next;
            end = end -> next;
        }
        return true;
    }
};

Lowest Common Ancestor of a Binary Search Tree

Problem:

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) {
            return NULL;
        } else if (root -> val == p ->val ||
                    root -> val == q -> val ||
                    (root -> val > p -> val && root -> val < q -> val) ||
                    (root -> val > q -> val && root -> val < p -> val)) {
            return root;
        } else if (root -> val > p -> val &&
                    root -> val > q -> val) {
            return lowestCommonAncestor(root -> left, p, q);
        } else {
            return lowestCommonAncestor(root -> right, p, q);
        }
    }
};

=== Nicer one ===

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }

==== Another one =====

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q || root == NULL) {
            return root;
        }
        
        if ((p -> val < root -> val && q -> val > root -> val) ||
            (p -> val > root -> val && q -> val < root -> val)) {
            return root;
        } else if (root -> val > p -> val && root -> val > q -> val) {
            return lowestCommonAncestor(root -> left, p, q);
        } else {
            return lowestCommonAncestor(root -> right, p, q);
        }
    }

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if (node == NULL)
            return;
        if (node -> next != NULL) {
            ListNode* temp = node -> next;
            node -> val = node -> next -> val;
            node -> next = node -> next -> next;
            delete(temp);
        }
        return;
    }
};

Valid Anagrams

Problem:

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Solution:
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.empty() && t.empty())
            return true;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

Another one:

1. class Solution {  
2. public:  
3.     bool isAnagram(string s, string t) {  
4.         int len1 = s.length();  
5.         int len2 = t.length();  
6.         if(len1!=len2){  
7.             return false;  
8.         }  
9.         vector<int> count(26, 0);  
10.         for(int i=0; i<len1; i++){  
11.             count[s[i]-'a']++;  
12.         }  
13.         for(int i=0; i<len2; i++){  
14.             if(--count[t[i]-'a']<0){  
15.                 return false;  
16.             }  
17.         }  
18.         return true;  
19.     }  
20. };  

======= Another one =====

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }
        unordered_map<char, int> mp;
       
        for (auto ch: s) {
            mp[ch]++;
        }
       
        for (auto ch: t) {
            if (!mp.count(ch)) {
                return false;
            }
            mp[ch]--;
            if (mp[ch] < 0) {
                return false;
            }
        }
       
        return true;
    }
};