Same Tree Solutions in C++

// Source : https://oj.leetcode.com/problems/same-tree/
// Author : Hao Chen
// Date   : 2014-06-27



/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    Solution(){
        srand(time(NULL));
    }
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (random()%2){
            return isSameTree1(p, q);
        }
        return isSameTree2(p, q);
    }
    
    bool isSameTree1(TreeNode *p, TreeNode *q) {
        if(!p && !q) return true;  
        if(!p || !q) return false;  
        return (p->val == q->val) &&  
                isSameTree(p->left, q->left) &&   
                isSameTree(p->right, q->right);
    }
    
    bool isSameTree2(TreeNode *p, TreeNode *q) {
        
        queue<TreeNode*> q1, q2;
        q1.push(p);
        q2.push(q);
        while (q1.size()>0 && q2.size()>0 ){
            TreeNode* p1 = q1.front();
            q1.pop();
            TreeNode* p2 = q2.front();
            q2.pop();
            if (!p1 && !p2) continue;
            if (!p1 || !p2)  return false;

            if ( p1->val != p2->val) {
                return false;
            }

            q1.push(p1->left);
            q2.push(p2->left);

            q1.push(p1->right);
            q2.push(p2->right);

        }
        return true;
    }
};

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
 struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
 
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p && q) return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        else if (!p && !q) return true;
        else return false;
    }
};

/// Source : https://leetcode.com/problems/same-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-10-16

#include <iostream>

using namespace std;


/// Using a string to represent a Binary Tree in preorder
/// Time Complexity: O(n)
/// Space Complexity: O(h)

/// 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {

        string ps = "#";
        getTreeString(p, ps);

        string qs = "#";
        getTreeString(q, qs);

        return ps == qs;
    }

private:
    void getTreeString(TreeNode* node, string& s){

        if(!node){
            s += "NULL#";
            return;
        }

        s += to_string(node->val) + "#";
        getTreeString(node->left, s);
        getTreeString(node->right, s);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/same-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-10-16

#include <iostream>

using namespace std;


/// Recursion
/// Time Complexity: O(n)
/// Space Complexity: O(h)

/// 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {

        if(!p && !q) return true;
        if(!p || !q) return false;
        if(p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/same-tree/description/
/// Author : liuyubobobo
/// Time   : 2019-03-11

#include <iostream>
#include <stack>

using namespace std;


/// Iterative
/// Time Complexity: O(n)
/// Space Complexity: O(h)

/// 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {

        stack<TreeNode*> stack1, stack2;
        stack1.push(p), stack2.push(q);
        while(!stack1.empty() || !stack2.empty()){
            TreeNode* cur1 = stack1.top();
            stack1.pop();

            TreeNode* cur2 = stack2.top();
            stack2.pop();

            if(cur1 && !cur2) return false;
            if(!cur1 && cur2) return false;
            if(!cur1 && !cur2) continue;

            if(cur1->val != cur2->val) return false;
            stack1.push(cur1->right);
            stack1.push(cur1->left);
            stack2.push(cur2->right);
            stack2.push(cur2->left);
        }

        return stack1.empty() && stack2.empty();
    }
};


int main() {

    return 0;
}