[LeetCode] Serialize and Deserialize Binary Tree

Question can be found
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

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

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL) return "";
        vector<string> v;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode *t = q.front();
            q.pop();
            if(t == NULL) {
                v.push_back("null");
                continue;
            }
            
            v.push_back(to_string(t->val));
            
            q.push(t->left);
            q.push(t->right);
        }
        
        int l = v.size() - 1;
        while(v[l] == "null") l--;
        
        string res = v[0];
        for(int i=1;i<=l;i++){
            res += "," + v[i];
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(0 == data.length()) return NULL;
        vector<string> v;
        int start = 0;
        for(int i=1;i<data.length();i++) {
            if(data[i] != ',') continue;
            v.push_back(data.substr(start, i-start));
            start = i+1;
        }
        v.push_back(data.substr(start));
        int index = 0;
        
        TreeNode *node = new TreeNode(stoi(v[index]));
        
        queue<TreeNode*> nodesOnLevel;
        int count = v.size();
        nodesOnLevel.push(node);
        
        while(!nodesOnLevel.empty()) {
            int size = nodesOnLevel.size();
            for(int i=0;i<size;i++){
                
                int left = index + 1;
                if(left >= count) return node;
                if(v[left] != "null") {
                    TreeNode *cur = new TreeNode(stoi(v[left]));
                    nodesOnLevel.front()->left = cur;
                    nodesOnLevel.push(cur);
                }
                
                int right = index + 2;
                if(right >= count) return node;
                if(v[right] != "null") {
                    TreeNode *cur = new TreeNode(stoi(v[right]));
                    nodesOnLevel.front()->right = cur;
                    nodesOnLevel.push(cur);
                }
                nodesOnLevel.pop();
                index += 2;
            }
        }
        
        return node;
    }
};

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

[LeetCode] Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

DFS :

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
private:
    typedef unordered_map<UndirectedGraphNode*,UndirectedGraphNode*> GraphMap;
    UndirectedGraphNode * clone(UndirectedGraphNode* node, GraphMap &map)
    {
        if(map.count(node)) return map[node];
        UndirectedGraphNode* newNode = new UndirectedGraphNode(node->label);
        map[node] = newNode;
        for(auto neighbor : node->neighbors)
        {
            UndirectedGraphNode* one = clone(neighbor, map);
            newNode->neighbors.push_back(one);
        }
        return newNode;
    }
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(NULL == node) return NULL;
        GraphMap map;
        return clone(node, map);
    }
};

BFS :

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:    
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(NULL == node) return NULL;
        queue<UndirectedGraphNode*> visit;
        GraphMap map;
        visit.push(node);
        UndirectedGraphNode * newCopy = new UndirectedGraphNode(node->label);
        map[node] = newCopy;
       
        while(!visit.empty())
        {
            UndirectedGraphNode *cur = visit.front();
            visit.pop();

            for(auto neighbor : cur->neighbors)
            {
                UndirectedGraphNode * newNeighbor;
                if(map.count(neighbor))
                {
                    newNeighbor = map[neighbor];
                }
                else
                {
                    newNeighbor = new UndirectedGraphNode(neighbor->label);
                    visit.push(neighbor);
                    map[neighbor] = newNeighbor;
                }
                map[cur]->neighbors.push_back(newNeighbor);
            }
        }
        
        return map[node];
    }
};

[LeetCode] Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(!root) return;
        queue<TreeLinkNode*> q;
        q.push(root);
        while(!q.empty())
        {
            TreeLinkNode * last = NULL;
            int size = q.size();
            for(int i=0;i<size;i++)
            {
                TreeLinkNode * curr = q.front();
                q.pop();
                if(last) last->next = curr;
                last = curr;
                if(curr->left) q.push(curr->left);
                if(curr->right) q.push(curr->right);
            }
        }
    }
};

[LeetCode] Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

DFS Solution:

class Solution {
public:
    void generate(vector<string> & res, string one, 
                  int left, int right, int n)
    {
        if(left == n && right == n)
        {
            res.push_back(one);
            return;
        }
        if(left < n)
        {
            generate(res, one+'(', left+1,right, n);
        }
        if(left > right)
        {
            generate(res, one +')', left,right+1, n);
        }
    }

    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        generate(res, "", 0,0,n);
        return res;
    }
};

BFS Solution :
find the last occurrence position P of '(' in the previous result, and append '(' + the rest + ')' to it from P+1 to end;

class Solution {
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> res;
        res.push_back("");
        for(int i=0;i<n;i++)
        {
            vector<string> tmp;
            for(int j=0;j<res.size();j++)
            {
                int pos = res[j].rfind('(');
                for(int k=pos+1;k<=res[j].size();k++)
                {
                    tmp.push_back(res[j].substr(0,k) +
                        '(' + res[j].substr(k) + ')');
                }
            }
            res = tmp;
        }
        return res;
    }
};

[LeetCode] Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode *root) 
    {
        vector<int> res;
        if(root == NULL) return res;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            for(int i=0;i<size;i++)
            {
                TreeNode *node = que.front();
                // the first element in the queue
                // is the rightmost on that level
                if(0 == i)
                {
                    res.push_back(node->val);
                }
                if(node->right)
                {
                    que.push(node->right);
                }
                if(node->left)
                {
                    que.push(node->left);
                }
                que.pop();
            }
        }
        return res;
    }
};

[LeetCode/LintCode] Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if(digits.length() == 0) return res;
        
        string letters[] = {"1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        res.push_back("");
        for(int i=0;i<digits.length();i++)
        {
            int c = digits[i] - '0' - 1;
            int size = res.size();
            vector<string> tmp;
            
            for(int j=0;j<size;j++)
            {
                for(int k = 0;k<letters[c].length();k++)
                {
                    tmp.push_back(res[j] + letters[c][k]);
                }
            }
            res = tmp;
        }
        return res;
    }
};