#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <gtest/gtest.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

#define TreeLinkNode TreeNode

TreeNode* TreeDestroy(TreeNode *root)
{
    if(root == nullptr) return nullptr;

    if(root->left != nullptr)
    {
        TreeDestroy(root->left);
        root->left = nullptr;
    }
    if(root->right != nullptr)
    {
        TreeDestroy(root->right);
        root->right = nullptr;
    }
    if((root->left == nullptr) && (root->right == nullptr))
    {
        delete root;
    }

    return nullptr;
}

/*****************************************************************************
 * OJ's Binary Tree Serialization:
 * The serialization of a binary tree follows a level order traversal, where
 * '#' signifies a path terminator where no node exists below.
 * Here's an example:
 *   1
 *  / \
 * 2   3
 *     /
 *    4
 *     \
 *      5
 * The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
 ****************************************************************************/
static TreeNode* TreeNewByStringOJ(const char* s)
{
    TreeNode* root = NULL;
    TreeNode* p = NULL;
    int val = 0;
    std::queue<TreeNode*> q;
    int negative = 1;

    if(s == NULL) return NULL;
    if(*s != '{') return NULL;
    s++;
    while((*s != '\0') && (*s != ',') && (*s != '}'))
    {
        if(*s == '-')
        {
            negative = -1;
        }
        else
        {
            val = val * 10 + (*s - '0');
        }
        s++;
    }
    s++;

    root = new TreeNode(val * negative);
    q.push(root);
    while(!q.empty() && (*s != '\0'))
    {
        p = q.front(); q.pop();

        if(*s != '#')
        {
            val = 0;
            negative = 1;
            while((*s != ',') && (*s != '\0') && (*s != '}'))
            {
                if(*s == '-')
                {
                    negative = -1;
                }
                else
                {
                    val = val * 10 + (*s - '0');
                }
                s++;
            }
            s++;
            p->left = new TreeNode(val * negative);
            q.push(p->left);
        }
        else
        {
            s++; //jump '#'
            if(*s == '\0') break;
            s++; //jump ','
            if(*s == '\0') break;
        }

        if(*s == '\0') break;

        if(*s != '#')
        {
            val = 0;
            negative = 1;
            while((*s != ',') && (*s != '\0') && (*s != '}'))
            {
                if(*s == '-')
                {
                    negative = -1;
                }
                else
                {
                    val = val * 10 + (*s - '0');
                }
                s++;
            }
            s++;
            p->right = new TreeNode(val * negative);
            q.push(p->right);
        }
        else
        {
            s++; //jump '#'
            if(*s == '\0') break;
            s++; //jump ','
            if(*s == '\0') break;
        }
    }

    return root;
}

class MinStack {
private:
    stack<int> normal;
    stack<int> min;

public:
    void push(int x) {
        if(min.empty() || x <= min.top())
        {
            min.push(x);
        }
        normal.push(x);
    }

    void pop() {
        if(normal.top() == min.top())
        {
            min.pop();
        }
        normal.pop();
    }

    int top() {
        return normal.top();
    }

    int getMin() {
        return min.top();
    }
};

class TwoSum {
private:
    unordered_map<int, int> rec;

public:
    void add(int number) {
        rec[number]++;
    }

    bool find(int value) {
        for (auto it = rec.begin(); it != rec.end(); it++) {
            int val = value - it->first;
            if (val == it->first) {
                if (it -> second > 1) return true;
            } else {
                if (rec.find(val) != rec.end()) {
                    return true;
                }
            }
        }
        return false;
    }
};

class Solution
{
public:
    //006
    string convert(string s, int nRows) {
        int i = 0;
        unsigned int j = 0;
        bool flag = true;
        string result;

        if(s.size() == 0) return s;
        if(nRows <= 1) return s;

        for(i = 0; i < nRows; i++)
        {
            j = i;
            flag = true;
            while(j < s.size())
            {
                result.push_back(s[j]);
                if((i == 0) || (i == (nRows - 1)))
                {
                    j = j + 2 * (nRows - 1);
                }
                else
                {
                    if(flag)
                    {
                        flag = false;
                        j = j + 2 * (nRows - i - 1);
                    }
                    else
                    {
                        flag = true;
                        j = j + 2 * i;
                    }
                }
            }
        }

        return result;
    }

    //014
    string longestCommonPrefix(vector<string> &strs) {
        char prefix[256] = {0};
        unsigned int i = 0;
        int j = 0;

        if(strs.size() == 0) return string(prefix);

        strcpy(prefix, strs[0].c_str());
        for(i = 1; i < strs.size(); i++)
        {
            for(j = 0; (prefix[j] != '\0') && (strs[i][j] != '\0'); j++)
            {
                if(prefix[j] != strs[i][j])
                {
                    break;
                }
            }
            prefix[j] = '\0';
        }

        return string(prefix);
    }

    //020
    bool isValid(string s) {
        stack<int> ss;
        int open;
        const char* p = nullptr;

        p = s.c_str();
        if(p == NULL) return false;
        if(*p == '\0') return false;

        while(*p != '\0')
        {
            if((*p == '{') || (*p == '(') || (*p == '['))
            {
                ss.push(*p);
                p++;
                continue;
            }

            if(ss.empty())
            {
                return false;
            }
            else if(*p == '}')
            {
                open = ss.top();ss.pop();
                if(open != '{') return false;
            }
            else if(*p == ')')
            {
                open = ss.top(); ss.pop();
                if(open != '(') return false;
            }
            else if(*p == ']')
            {
                open = ss.top(); ss.pop();
                if(open != '[') return false;
            }
            p++;
        }

        if(!ss.empty()) return false;
        else return true;
    }

    //036
    bool isValidSudoku(vector<vector<char>> &board) {
        unsigned int i = 0;
        unsigned int j = 0;
        int m = 0;
        int n = 0;
        int r = 0;
        int c = 0;
        char cell[9] = {0};

        if(board.size() != 9)
        {
            return false;
        }

        for(i = 0; i < board.size(); i++)
        {
            if(board[i].size() != 9)
            {
                return false;
            }
        }

        for(i = 0; i < 9; i++)
        {
            memset(cell, 0, sizeof(cell));
            for(j = 0; j < 9; j++)
            {
                if((board[i][j] != '.') && (board[i][j] >= '1') && (board[i][j] <= '9'))
                {
                    if(cell[board[i][j] - '0' - 1] != 0)
                    {
                        return false;
                    }
                    else
                    {
                        cell[board[i][j] - '0' - 1] = 1;
                    }
                }
            }
        }

        for(i = 0; i < 9; i++)
        {
            memset(cell, 0, sizeof(cell));
            for(j = 0; j < 9; j++)
            {
                if((board[j][i] != '.') && (board[j][i] >= '1') && (board[j][i] <= '9'))
                {
                    if(cell[board[j][i] - '0' - 1] != 0)
                    {
                        return false;
                    }
                    else
                    {
                        cell[board[j][i] - '0' - 1] = 1;
                    }
                }
            }
        }

        //行序号为(i - 1) / 3 *3 到(i - 1) / 3 *3+2
        //列序号为(i - 1)%3 *3 到(i - 1)%3 *3+2
        for(i = 1; i <= 9; i++)
        {
            memset(cell, 0, sizeof(cell));
            for(m = 0; m < 3; m++)
            {
                for(n = 0; n < 3; n++)
                {
                    r = (i - 1) / 3 * 3 + m;
                    c = (i - 1) % 3 * 3 + n;
                    if((board[r][c] != '.') && (board[r][c] >= '1') && (board[r][c] <= '9'))
                    {
                        if(cell[board[r][c] - '0' - 1] != 0)
                        {
                            return false;
                        }
                        else
                        {
                            cell[board[r][c] - '0' - 1] = 1;
                        }
                    }
                }
            }
        }

        return true;
    }

    //38
    string countAndSay(int n) {
        string _038_say;
        string _038_say2;
        char temp[128] = {0};
        const char* p = NULL;
        int i = 0;
        char current = 0;
        int num = 0;

        _038_say.push_back('1');

        for(i = 1; i < n; i++)
        {
            p = _038_say.c_str();
            while(*p)
            {
                current = *p;
                num = 0;
                while(current == *p)
                {
                    num++;
                    p++;
                }
                sprintf(temp, "%d%d", num, current - '0');
                _038_say2.append(temp);
            }
            _038_say.clear();
            _038_say.append(_038_say2.begin(), _038_say2.end());
            _038_say2.clear();
        }

        return _038_say;
    }

    //66
    vector<int> plusOne(vector<int> &digits) {
        int carray = 1;
        int val = 0;
        vector<int> result;

        if(digits.size() == 0) return result;

        do
        {
            val = digits.back() + carray;
            carray = val / 10;
            val = val % 10;
            result.insert(result.begin(), val);
            digits.pop_back();
        }while(!digits.empty() && carray != 0);

        while(!digits.empty())
        {
            result.insert(result.begin(), digits.back());
            digits.pop_back();
        }

        if(carray != 0)
        {
            result.insert(result.begin(), carray);
        }

        return result;
    }

    //067
    string addBinary(string a, string b) {
        int carray = 0;
        int val = 0;
        string c;
        const char* pa = nullptr;
        const char* pb = nullptr;

        if(a.size() == 0 && b.size() == 0) return string("");
        if(a.size() == 0 && b.size() != 0) return b;
        if(a.size() != 0 && b.size() == 0) return a;

        reverse(b.begin(), b.end());
        reverse(a.begin(), a.end());

        pa = a.c_str();
        pb = b.c_str();

        while(*pa && *pb)
        {
            val = carray + *pa - '0' + *pb - '0';
            carray = val / 2;
            c.push_back('0' + val % 2);
            pa++;
            pb++;
        }

        while(*pa)
        {
            val = carray + *pa - '0';
            carray = val / 2;
            c.push_back('0' + val % 2);
            pa++;
        }

        while(*pb)
        {
            val = carray + *pb - '0';
            carray = val / 2;
            c.push_back('0' + val % 2);
            pb++;
        }

        if(carray != 0) c.push_back('1');
        reverse(c.begin(), c.end());

        return c;
    }

    //078
    vector<vector<int>> subsets(vector<int> &S) {
        int max = 1<<S.size();
        vector<vector<int> >result;
        sort(S.begin(), S.end());
        for(int i = 0;i < max;i++)
        {
            vector<int> temp;
            int idx = 0;
            int j = i;
            while(j > 0)
            {
                if(j&1)
                {
                    temp.push_back(S[idx]);
                }
                idx++;
                j = j >> 1;
            }
            result.push_back(temp);
        }
        return result;
    }

    //094
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> v;
        stack<TreeNode*> s;
        TreeNode* p = nullptr;

        if(root == nullptr) return v;

        p = root;
        while((p != nullptr) || !s.empty())
        {
            while(p != nullptr)
            {
                s.push(p);
                p = p->left;
            }
            if(!s.empty())
            {
                p = s.top(); s.pop();
                v.push_back(p->val);
                p = p->right;
            }
        }

        return v;
    }

    //98
    bool isValidBST(TreeNode *root) {
        stack<TreeNode*> s;
        TreeNode* p = nullptr;
        int64_t last_val = INT64_MIN;
        bool status = true;

        if(root == nullptr) return true;

        p = root;
        while((p != nullptr) || (!s.empty()))
        {
            while(p != nullptr)
            {
                s.push(p);
                p = p->left;
            }

            if(!s.empty())
            {
                p = s.top(); s.pop();
                if(p->val <= last_val)
                {
                    status = false;
                    break;
                }
                last_val = p->val;
                p = p->right;
            }
        }

        return status;
    }

    //101
    bool isSymmetric(TreeNode *root) {
        queue<TreeNode*>* q = NULL;
        queue<TreeNode*>* q2 = NULL;
        queue<TreeNode*>* temp = NULL;
        TreeNode* p = NULL;
        TreeNode* p2 = NULL;
        vector<TreeNode*> array;
        int size = 0;
        int index = 0;
        bool status = true;

        if(root == NULL) return true;

        q = new queue<TreeNode*>;
        q2 = new queue<TreeNode*>;

        q->push(root);
        while(!q->empty() && status)
        {
            while(!q->empty())
            {
                p = q->front(); q->pop();
                if(p != NULL)
                {
                    if(p->left != NULL) q2->push(p->left);
                    if(p->right != NULL) q2->push(p->right);
                    array.push_back(p->left);
                    array.push_back(p->right);
                }
                else
                {
                    array.push_back(NULL);
                    array.push_back(NULL);
                }
            }

            size = array.size();
            if(size % 2 != 0)
            {
                status = false;
                break;
            }

            for(index = 0; index < size / 2; index++)
            {
                p = array[index];
                p2 = array[size - index - 1];
                if(((p == NULL) && (p2 != NULL))
                        || ((p != NULL) && (p2 == NULL)))
                {
                    status = false;
                    break;
                }

                if((p != NULL) && (p2 != NULL) && (p->val != p2->val))
                {
                    status = false;
                    break;
                }
            }

            array.clear();
            temp = q2;
            q2 = q;
            q = temp;
        }

        delete(q);
        delete(q2);
        return status;
    }

    //102
    vector<vector<int>> levelOrder(TreeNode *root) {
        vector<vector<int>> v;
        vector<int>* a;
        TreeNode* p = NULL;
        queue<TreeNode*> *q;
        queue<TreeNode*> *q2;
        queue<TreeNode*> *temp;

        if(root == NULL) return v;

        q = new queue<TreeNode*>;
        q2 = new queue<TreeNode*>;

        q->push(root);
        while(!q->empty())
        {
            a = new vector<int>;

            while(!q->empty())
            {
                p = q->front(); q->pop();
                a->push_back(p->val);
                if(p->left != NULL) q2->push(p->left);
                if(p->right != NULL) q2->push(p->right);
            }

            v.push_back(*a);
            temp = q2;
            q2 = q;
            q = temp;
        }
        delete q;
        delete q2;

        return v;
    }

    //107
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int>> v;
        queue<TreeNode*>* q;
        queue<TreeNode*>* q2;
        queue<TreeNode*>* q3;
        queue<TreeNode*>* temp;
        stack<queue<TreeNode*>*> s;
        TreeNode* p;
        vector<int>* a;

        if(root == NULL) return v;

        q = new queue<TreeNode*>;
        q2 = new queue<TreeNode*>;
        q3 = new queue<TreeNode*>;
        q3->push(root);
        q->push(root);
        s.push(q3);

        while(!q->empty())
        {
            q3 = new queue<TreeNode*>;
            while(!q->empty())
            {
                p = q->front();q->pop();
                if(p->left != NULL)
                {
                    q2->push(p->left);
                    q3->push(p->left);
                }
                if(p->right != NULL)
                {
                    q2->push(p->right);
                    q3->push(p->right);
                }
            }

            if(!q3->empty())
            {
                s.push(q3);
            }

            temp = q2;
            q2 = q;
            q = temp;
        }

        while(!s.empty())
        {
            temp = s.top();
            a = new vector<int>;
            while(!temp->empty())
            {
                p = temp->front(); temp->pop();
                a->push_back(p->val);
            }
            v.push_back(*a);
            s.pop();
        }

        delete q;
        delete q2;

        return v;
    }

    //114
    void flatten(TreeNode *root) {
        stack<TreeNode*> s;
        TreeNode* p = nullptr;
        TreeNode* q = nullptr;

        if(root == nullptr) return;
        s.push(root);
        while(!s.empty())
        {
            p = s.top(); s.pop();
            if(p->right != nullptr) s.push(p->right);
            if(p->left != nullptr) s.push(p->left);
            p->left = p->right = nullptr;
            if(q == nullptr)
            {
                q = p;
            }
            else
            {
                q->right = p;
                q = q->right;
            }
        }
    }

    //116
    void connect(TreeLinkNode *root){
        queue<TreeLinkNode*>* q1 = NULL;
        queue<TreeLinkNode*>* q2 = NULL;
        queue<TreeLinkNode*>* temp = NULL;
        TreeLinkNode* p1 = NULL;
        TreeLinkNode* p2 = NULL;

        if(root == NULL) return;

        q1 = new queue<TreeLinkNode*>;
        q2 = new queue<TreeLinkNode*>;

        q1->push(root);
        while(!q1->empty())
        {
            while(!q1->empty())
            {
                p1 = q1->front(); q1->pop();
                if(p2 == NULL)
                {
                    p2 = p1;
                }
                else
                {
                    p2->next = p1;
                    p2 = p2->next;
                }
                if(p1->left != NULL)
                {
                    q2->push(p1->left);
                }
                if(p1->right != NULL)
                {
                    q2->push(p1->right);
                }
            }
            p2 = NULL;
            temp = q2;
            q2 = q1;
            q1 = temp;
        }
        delete q1;
        delete q2;
    }

    //118
    vector<vector<int>> generate(int numRows)
    {
        vector<vector<int>> rows;
        vector<int>* row = NULL;
        vector<int>* last = NULL;
        int i = 0;
        int j = 0;

        if(numRows <= 0) return rows;

        for(i = 0; i < numRows; i++)
        {
            row = new vector<int>;
            row->push_back(1);
            for(j = 1; j <= i; j++)
            {
                if(j == i)
                {
                    row->push_back(1);
                }
                else
                {
                    row->push_back(last->at(j) + last->at(j - 1));
                }
            }
            last = row;
            rows.push_back(*row);
        }

        return rows;
    }

    //119
    vector<int> getRow(int rowIndex) {
        int i = 0;
        int j = 0;
        vector<int> row(rowIndex + 1);

        if(rowIndex < 0) return row;

        row[0] = 1;
        for(i = 1; i <= rowIndex; i++)
        {
            for(j = i; j > 0; j--)
            {
                if(i == j)
                {
                    row[j] = 1;
                }
                else
                {
                    row[j] = row[j] + row[j - 1];
                }
            }
        }

        return row;
    }

    //144
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> v;
        stack<TreeNode*> s;
        TreeNode* p;

        if(root == NULL) return v;

        s.push(root);
        while(!s.empty())
        {
            p = s.top(); s.pop();
            v.push_back(p->val);
            if(p->right != NULL) s.push(p->right);
            if(p->left != NULL) s.push(p->left);
        }

        return v;
    }
};

TEST(LeetCode, _006_convert)
{
    string r;
    Solution s;

    r = s.convert("PAYPALISHIRING", 3);
    EXPECT_EQ(r, string("PAHNAPLSIIGYIR"));
}

TEST(LeetCode, _014_longest_common_prefix)
{
    Solution s;
    vector<string> a;
    vector<string> b;
    vector<string> c;
    vector<string> d;
    vector<string> e;

    a.push_back("ab");
    a.push_back("ab1");
    a.push_back("ab2");

    b.push_back("abc");
    b.push_back("abdefsd");
    b.push_back("ab");

    c.push_back("abesdfsasdf");
    c.push_back("abesxxxxysdfs");
    c.push_back("abes1");

    d.push_back("asdfes");
    d.push_back("bdefes");
    d.push_back("cdfeasd");

    e.push_back("aa");
    e.push_back("a");

    EXPECT_EQ(s.longestCommonPrefix(a), "ab");
    EXPECT_EQ(s.longestCommonPrefix(b), "ab");
    EXPECT_EQ(s.longestCommonPrefix(c), "abes");
    EXPECT_EQ(s.longestCommonPrefix(d), "");
    EXPECT_EQ(s.longestCommonPrefix(e), "a");
}

TEST(LeetCode, _020_is_valid)
{
    Solution s;

    //EXPECT_EQ(s.isValid(NULL), false);
    EXPECT_EQ(s.isValid(string("")), false);
    EXPECT_EQ(s.isValid(string("]")), false);
    EXPECT_EQ(s.isValid(string("}")), false);
    EXPECT_EQ(s.isValid(string(")")), false);
    EXPECT_EQ(s.isValid(string("[]")), true);
    EXPECT_EQ(s.isValid(string("[)")), false);
    EXPECT_EQ(s.isValid(string("(){}[]")), true);
    EXPECT_EQ(s.isValid(string("((}}")), false);
    EXPECT_EQ(s.isValid(string("(({}))[[()]]")), true);
}

TEST(LeetCode, _036_is_valid_sudoku)
{
    vector<vector<char>> s1;
    vector<vector<char>> s2;
    Solution s;
    vector<char>* c;
    char* a1[]= {
        (char*)".21......",
        (char*)"....6....",
        (char*)"......7..",
        (char*)"....5....",
        (char*)"..5......",
        (char*)"......3..",
        (char*)".........",
        (char*)"3...8.1..",
        (char*)"........8"
    };
    char* p = NULL;
    int i = 0;

    for(i = 0; i < 9; i++)
    {
        p = a1[i];
        c = new vector<char>;
        while(*p)
        {
            c->push_back(*p);
            p++;
        }

        s1.push_back(*c);
    }

    char* a2[] =
    {
        (char*)".87654321",
        (char*)"2........",
        (char*)"3........",
        (char*)"4........",
        (char*)"5........",
        (char*)"6........",
        (char*)"7........",
        (char*)"8........",
        (char*)"9........"
    };
    for(i = 0; i < 9; i++)
    {
        p = a2[i];
        c = new vector<char>;
        while(*p)
        {
            c->push_back(*p);
            p++;
        }

        s2.push_back(*c);
    }
    EXPECT_EQ(s.isValidSudoku(s1), true);
    EXPECT_EQ(s.isValidSudoku(s2), true);
}

TEST(LeetCode, _038_count_and_say)
{
    Solution s;

    EXPECT_EQ("1", s.countAndSay(1));
    EXPECT_EQ("11", s.countAndSay(2));
    EXPECT_EQ("21", s.countAndSay(3));
    EXPECT_EQ("1211", s.countAndSay(4));
    EXPECT_EQ("111221", s.countAndSay(5));
}

TEST(LeetCode, _066_plus_one)
{
    Solution s;
    int a1[] = {6,2,7,9};
    vector<int> v1(a1, a1 + sizeof(a1) / sizeof(int));
    vector<int> res;
    vector<int> v2;

    v2.push_back(9);
    res = s.plusOne(v2);
    EXPECT_EQ((unsigned int)2, res.size());
    EXPECT_EQ(1, res[0]);
    EXPECT_EQ(0, res[1]);

    res = s.plusOne(v1);
    EXPECT_EQ((unsigned int)4, res.size());
    EXPECT_EQ(6, res[0]);
    EXPECT_EQ(2, res[1]);
    EXPECT_EQ(8, res[2]);
    EXPECT_EQ(0, res[3]);
}

TEST(LeetCode, _067_add_binary)
{
    Solution s;

    EXPECT_EQ(s.addBinary("", ""), "");
    EXPECT_EQ(s.addBinary("11", ""), "11");
    EXPECT_EQ(s.addBinary("", "11"), "11");
    EXPECT_EQ(s.addBinary("11", "1"), "100");
    EXPECT_EQ(s.addBinary("101", "1"), "110");
}

TEST(LeetCode, _078_subsets)
{
    vector<int> S;
    vector<vector<int>> result;
    Solution s;

    S.push_back(1);
    S.push_back(2);
    S.push_back(3);
    result = s.subsets(S);
    EXPECT_EQ(result.size(), (unsigned int)8);
}

TEST(LeetCode, _094_inorder_traversal)
{
    TreeNode* t = nullptr;
    vector<int> v;
    Solution s;

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1,#,2,3}"));
    v = s.inorderTraversal(t);
    EXPECT_EQ((unsigned int)3, v.size());
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(3, v[1]);
    EXPECT_EQ(2, v[2]);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));
}

TEST(LeetCode, _098_is_valid_bst)
{
    TreeNode* t = NULL;
    Solution s;

    EXPECT_EQ(s.isValidBST(NULL), true);

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1}"));
    EXPECT_EQ(s.isValidBST(t), true);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1,2}"));
    EXPECT_EQ(s.isValidBST(t), false);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1,1}"));
    EXPECT_EQ(s.isValidBST(t), false);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{3,#,2}"));
    EXPECT_EQ(s.isValidBST(t), false);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{4,2,6,1,3,5,7}"));
    EXPECT_EQ(s.isValidBST(t), true);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{10,5,15,#,#,6,20}"));
    EXPECT_EQ(s.isValidBST(t), false);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{-2147483648}"));
    EXPECT_EQ(s.isValidBST(t), true);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{-2147483648,#,2147483647}"));
    EXPECT_EQ(s.isValidBST(t), true);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));
}

TEST(LeetCode, _101_is_symmetric)
{
    TreeNode* t = nullptr;
    Solution s;

    EXPECT_EQ(true, s.isSymmetric(nullptr));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1}"));
    EXPECT_EQ(true, s.isSymmetric(t));
    ASSERT_EQ(nullptr, TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1,2,2,3,4,4,3}"));
    EXPECT_EQ(true, s.isSymmetric(t));
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1,2,2,#,3,#,3}"));
    EXPECT_EQ(0, s.isSymmetric(t));
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1,2}"));
    EXPECT_EQ(0, s.isSymmetric(t));
    ASSERT_EQ(nullptr, t = TreeDestroy(t));
}

TEST(LeetCode, _102_level_order)
{
    TreeNode* t = NULL;
    vector<vector<int>> v;
    Solution s;

    /*************************************************************************
     * Input:{3,9,20,#,#,15,7}, Output:[[3],[9,20],[15,7]]
     ************************************************************************/
    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{3,9,20,#,#,15,7}"));
    v = s.levelOrder(t);
    ASSERT_EQ((unsigned int)3, v.size());
    EXPECT_EQ((unsigned int)1, v[0].size());
    EXPECT_EQ(3, v[0][0]);
    EXPECT_EQ((unsigned int)2, v[1].size());
    EXPECT_EQ(9, v[1][0]);
    EXPECT_EQ(20, v[1][1]);
    EXPECT_EQ((unsigned int)2, v[2].size());
    EXPECT_EQ(15, v[2][0]);
    EXPECT_EQ(7, v[2][1]);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));

    /*************************************************************************
     * Input:{1,2,3,4,5}, Output:[[1],[2,3],[4,5]]
     ************************************************************************/
    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1,2,3,4,5}"));
    v = s.levelOrder(t);
    ASSERT_EQ((unsigned int)3, v.size());
    EXPECT_EQ((unsigned int)1, v[0].size());
    EXPECT_EQ(1, v[0][0]);
    EXPECT_EQ((unsigned int)2, v[1].size());
    EXPECT_EQ(2, v[1][0]);
    EXPECT_EQ(3, v[1][1]);
    EXPECT_EQ((unsigned int)2, v[2].size());
    EXPECT_EQ(4, v[2][0]);
    EXPECT_EQ(5, v[2][1]);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));
}

TEST(LeetCode, _107_level_order_bottom)
{
    TreeNode* t = NULL;
    vector<vector<int>> v;
    Solution s;

    /*************************************************************************
     * Input:{3,9,20,#,#,15,7}, Output:[[15,7],[9,20],[3]]
     ************************************************************************/
    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{3,9,20,#,#,15,7}"));
    v = s.levelOrderBottom(t);
    ASSERT_EQ((unsigned int)3, v.size());
    ASSERT_EQ((unsigned int)2, v[0].size());
    EXPECT_EQ(15, v[0][0]);
    EXPECT_EQ(7, v[0][1]);
    ASSERT_EQ((unsigned int)2, v[1].size());
    EXPECT_EQ(9, v[1][0]);
    EXPECT_EQ(20, v[1][1]);
    ASSERT_EQ((unsigned int)1, v[2].size());
    EXPECT_EQ(3, v[2][0]);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));
}

TEST(LeetCode, _114_flatten)
{
    TreeNode* t = nullptr;
    Solution s;

    t = TreeNewByStringOJ("{1}");
    ASSERT_NE(nullptr, t);
    s.flatten(t);
    ASSERT_NE(nullptr, t);
    EXPECT_EQ(1, t->val);
    TreeDestroy(t);

    t = TreeNewByStringOJ("{1,2,5,3,4,#,6}");
    ASSERT_NE(nullptr, t);
    s.flatten(t);
    ASSERT_NE(nullptr, t);
    EXPECT_EQ(1, t->val);
    EXPECT_EQ(2, t->right->val);
    EXPECT_EQ(3, t->right->right->val);
    EXPECT_EQ(4, t->right->right->right->val);
    EXPECT_EQ(5, t->right->right->right->right->val);
    EXPECT_EQ(6, t->right->right->right->right->right->val);
    TreeDestroy(t);
}

TEST(LeetCode, _116_connect)
{
    TreeLinkNode* t = NULL;
    Solution s;

    ASSERT_NE(nullptr, t = TreeNewByStringOJ("{1,2,3,4,5,6,7}"));
    s.connect(t);
    EXPECT_EQ(t->val, 1);
    EXPECT_EQ(t->next, nullptr);
    EXPECT_EQ(t->left->val, 2);
    EXPECT_EQ(t->left->next->val, 3);
    EXPECT_EQ(t->right, t->left->next);
    EXPECT_EQ(t->left->left->val, 4);
    EXPECT_EQ(t->left->left->next->val, 5);
    EXPECT_EQ(t->left->left->next, t->left->right);
    EXPECT_EQ(t->right->left->val, 6);
    EXPECT_EQ(t->right->right, t->right->left->next);
    EXPECT_EQ(t->right->left->next->val, 7);
    EXPECT_EQ(t->left->left->next->next->val, 6);
    EXPECT_EQ(t->left->left->next->next->next->val, 7);
    ASSERT_EQ(nullptr, t = TreeDestroy(t));
}

TEST(LeetCode, _118_generate)
{
    vector<vector<int>> rows;
    Solution s;

    rows = s.generate(4);
    EXPECT_EQ((unsigned int)4, rows.size());
    EXPECT_EQ((unsigned int)4, rows[3].size());
    EXPECT_EQ(1, rows[3][0]);
    EXPECT_EQ(3, rows[3][1]);
    EXPECT_EQ(3, rows[3][2]);
    EXPECT_EQ(1, rows[3][3]);
}

TEST(LeetCode, _119_get_row)
{
    vector<int> r;
    Solution s;

    r = s.getRow(0);
    EXPECT_EQ(r.size(), (unsigned int)1);
    EXPECT_EQ(r[0], 1);

    r = s.getRow(3);
    EXPECT_EQ(r.size(), (unsigned int)4);
    EXPECT_EQ(r[0], 1);
    EXPECT_EQ(r[1], 3);
    EXPECT_EQ(r[2], 3);
    EXPECT_EQ(r[3], 1);

    r = s.getRow(4);
    EXPECT_EQ(r.size(), (unsigned int)5);
    EXPECT_EQ(r[0], 1);
    EXPECT_EQ(r[1], 4);
    EXPECT_EQ(r[2], 6);
    EXPECT_EQ(r[3], 4);
    EXPECT_EQ(r[4], 1);

    r = s.getRow(5);
    EXPECT_EQ(r.size(), (unsigned int)6);
    EXPECT_EQ(r[0], 1);
    EXPECT_EQ(r[1], 5);
    EXPECT_EQ(r[2], 10);
    EXPECT_EQ(r[3], 10);
    EXPECT_EQ(r[4], 5);
    EXPECT_EQ(r[5], 1);

    r = s.getRow(13);
    EXPECT_EQ(r.size(), (unsigned int)14);
    EXPECT_EQ(r[0], 1);
    EXPECT_EQ(r[1], 13);
    EXPECT_EQ(r[2], 78);
    EXPECT_EQ(r[3], 286);
    EXPECT_EQ(r[4], 715);
    EXPECT_EQ(r[5], 1287);
    EXPECT_EQ(r[6], 1716);
    EXPECT_EQ(r[7], 1716);
    EXPECT_EQ(r[8], 1287);
    EXPECT_EQ(r[9], 715);
    EXPECT_EQ(r[10], 286);
    EXPECT_EQ(r[11], 78);
    EXPECT_EQ(r[12], 13);
    EXPECT_EQ(r[13], 1);

    r = s.getRow(21);
    EXPECT_EQ(r.size(), (unsigned int)22);
    EXPECT_EQ(r[ 0], 1);
    EXPECT_EQ(r[ 1], 21);
    EXPECT_EQ(r[ 2], 210);
    EXPECT_EQ(r[ 3], 1330);
    EXPECT_EQ(r[ 4], 5985);
    EXPECT_EQ(r[ 5], 20349);
    EXPECT_EQ(r[ 6], 54264);
    EXPECT_EQ(r[ 7], 116280);
    EXPECT_EQ(r[ 8], 203490);
    EXPECT_EQ(r[ 9], 293930);
    EXPECT_EQ(r[10], 352716);
    EXPECT_EQ(r[11], 352716);
    EXPECT_EQ(r[12], 293930);
    EXPECT_EQ(r[13], 203490);
    EXPECT_EQ(r[14], 116280);
    EXPECT_EQ(r[15], 54264);
    EXPECT_EQ(r[16], 20349);
    EXPECT_EQ(r[17], 5985);
    EXPECT_EQ(r[18], 1330);
    EXPECT_EQ(r[19], 210);
    EXPECT_EQ(r[20], 21);
    EXPECT_EQ(r[21], 1);

    r = s.getRow(29);
    EXPECT_EQ(r.size(), (unsigned int)30);
    EXPECT_EQ(r[ 0], 1);
    EXPECT_EQ(r[ 1], 29);
    EXPECT_EQ(r[ 2], 406);
    EXPECT_EQ(r[ 3], 3654);
    EXPECT_EQ(r[ 4], 23751);
    EXPECT_EQ(r[ 5], 118755);
    EXPECT_EQ(r[ 6], 475020);
    EXPECT_EQ(r[ 7], 1560780);
    EXPECT_EQ(r[ 8], 4292145);
    EXPECT_EQ(r[ 9], 10015005);
    EXPECT_EQ(r[10], 20030010);
    EXPECT_EQ(r[11], 34597290);
    EXPECT_EQ(r[12], 51895935);
    EXPECT_EQ(r[13], 67863915);
    EXPECT_EQ(r[14], 77558760);
    EXPECT_EQ(r[15], 77558760);
    EXPECT_EQ(r[16], 67863915);
    EXPECT_EQ(r[17], 51895935);
    EXPECT_EQ(r[18], 34597290);
    EXPECT_EQ(r[19], 20030010);
    EXPECT_EQ(r[20], 10015005);
    EXPECT_EQ(r[21], 4292145);
    EXPECT_EQ(r[22], 1560780);
    EXPECT_EQ(r[23], 475020);
    EXPECT_EQ(r[24], 118755);
    EXPECT_EQ(r[25], 23751);
    EXPECT_EQ(r[26], 3654);
    EXPECT_EQ(r[27], 406);
    EXPECT_EQ(r[28], 29);
    EXPECT_EQ(r[29], 1);
}

TEST(LeetCode, _144_preorder_traversal)
{
    TreeNode* t = NULL;
    vector<int> v;
    Solution s;

    v = s.preorderTraversal(NULL);
    EXPECT_EQ((unsigned int)0, v.size());

    t = TreeNewByStringOJ("{1,#,2,3}");
    ASSERT_NE(nullptr, t);
    v= s.preorderTraversal(t);
    ASSERT_EQ((unsigned int)3, v.size());
    EXPECT_EQ(1, v[0]);
    EXPECT_EQ(2, v[1]);
    EXPECT_EQ(3, v[2]);
}

TEST(LeetCode, _155_min_stack)
{
    MinStack ms;

    ms.push(10);
    EXPECT_EQ(ms.getMin(), 10);
    ms.push(20);
    ms.push(9);
    ms.push(21);
    ms.push(8);
    EXPECT_EQ(ms.getMin(), 8);
}

TEST(LeetCode, _170_two_sum)
{
    TwoSum ts;

    ts.add(1);
    ts.add(3);
    ts.add(5);

    EXPECT_EQ(true, ts.find(4));
    EXPECT_EQ(0, ts.find(7));
}

TEST(LeetCode, _999_oj_binary_tree_serialization)
{
    TreeNode* t1 = NULL;

    t1 = TreeNewByStringOJ("{1,2,3,#,#,4,#,#,5}");
    EXPECT_EQ(t1->val, 1);
    EXPECT_EQ(t1->left->val, 2);
    EXPECT_EQ(t1->right->val, 3);
}

int main(int argc, char* argv[])
{
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}