Symmetric Tree Solutions in C++

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



/**
 * 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 isSymmetric(TreeNode *root) {
        if (root == NULL ) return true;
        return isSymmetric(root->left, root->right);
        
    }
    
    bool isSymmetric(TreeNode *p, TreeNode *q){
        if (random()%2){
           return isSymmetric1(p, q);
        }
        return isSymmetric2(p, q);
    }
    
    bool isSymmetric1(TreeNode *p, TreeNode *q){
        if (p==NULL && q==NULL) return true;
        if (p==NULL || q==NULL) return false;
        
        return (p->val == q->val) &&
                isSymmetric(p->left, q->right) &&
                isSymmetric(p->right, q->left);
    }
    
    bool isSymmetric2(TreeNode *p, TreeNode *q){

        queue<TreeNode*> q1;
        queue<TreeNode*> 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==NULL && p2==NULL) continue;
            if (p1==NULL || p2==NULL) return false;
            
            if (p1->val != p2->val) return false;
            
            q1.push(p1->left);
            q2.push(p2->right);

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

        }
        return true;
        
    }
    
};

#include <cstddef>
#include <stack>

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

class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if (root == NULL) return true;
        TreeNode *lt = root->left, *rt = root->right;
        for (std::stack<TreeNode*> stack; !stack.empty() || (lt&&rt); ) {
            if (lt && rt) {
                if (lt->val != rt->val) return false;
                stack.push(lt->right);stack.push(rt->left);
                lt = lt->left; rt = rt->right;
            }
            else if (lt || rt) return false;
            else {
                lt = stack.top(); stack.pop();
                rt = stack.top(); stack.pop();
            }
        }
        if (lt || rt) return false;
        else return true;
    }
};

/// Source : https://leetcode.com/problems/symmetric-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-06-02

#include <iostream>

using namespace std;

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

/// Recursive
/// Revert one child tree and see if the two child trees of the root are identical
///
/// Time Complexity: O(n)
/// Space Complexity: O(h)
class Solution {
public:
    bool isSymmetric(TreeNode* root) {

        if(root == NULL)
            return true;

        TreeNode* left = root->left;
        TreeNode* right = root->right;
        right = revert(right);

        return is_identical(left, right);
    }

private:
    TreeNode* revert(TreeNode* root){
        if(root == NULL)
            return NULL;

        swap(root->left, root->right);
        revert(root->left);
        revert(root->right);
        return root;
    }

    bool is_identical(TreeNode* root1, TreeNode* root2){

        if(root1 == NULL && root2 == NULL)
            return true;

        if(root1 == NULL || root2 == NULL)
            return false;

        if(root1->val != root2->val)
            return false;

        return is_identical(root1->left, root2->left) &&
               is_identical(root1->right, root2->right);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/symmetric-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-06-02

#include <iostream>

using namespace std;

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

/// Recursive
/// No need to revert one child tree
/// See if the two child trees of the root are mirror directly
///
/// Time Complexity: O(n)
/// Space Complexity: O(h)
class Solution {
public:
    bool isSymmetric(TreeNode* root) {

        if(root == NULL)
            return true;

        return is_mirror(root, root);
    }

private:
    bool is_mirror(TreeNode* root1, TreeNode* root2){

        if(root1 == NULL && root2 == NULL)
            return true;

        if(root1 == NULL || root2 == NULL)
            return false;

        if(root1->val != root2->val)
            return false;

        return is_mirror(root1->left, root2->right) &&
               is_mirror(root1->right, root2->left);
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/symmetric-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-06-02

#include <iostream>
#include <queue>

using namespace std;

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

/// Non-Recursive
/// Using two queues to level traverse the root in different directions
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    bool isSymmetric(TreeNode* root) {

        if(root == NULL)
            return true;

        queue<TreeNode*> q1, q2;
        q1.push(root);
        q2.push(root);
        while(!q1.empty() && !q2.empty()){
            TreeNode* node1 = q1.front();
            q1.pop();

            TreeNode* node2 = q2.front();
            q2.pop();

            if(node1 == NULL && node2 == NULL)
                continue;

            if(node1 == NULL || node2 == NULL)
                return false;

            if(node1->val != node2->val)
                return false;

            q1.push(node1->left);
            q1.push(node1->right);

            q2.push(node2->right);
            q2.push(node2->left);
        }

        return q1.empty() && q2.empty();
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/symmetric-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-06-02

#include <iostream>
#include <queue>

using namespace std;

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

/// Non-Recursive
/// Using one queues to level traverse the root in different directions
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    bool isSymmetric(TreeNode* root) {

        if(root == NULL)
            return true;

        queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        while(!q.empty()){
            TreeNode* node1 = q.front();
            q.pop();

            TreeNode* node2 = q.front();
            q.pop();

            if(node1 == NULL && node2 == NULL)
                continue;

            if(node1 == NULL || node2 == NULL)
                return false;

            if(node1->val != node2->val)
                return false;

            q.push(node1->left);
            q.push(node2->right);
            q.push(node1->right);
            q.push(node2->left);
        }

        return true;
    }
};


int main() {

    return 0;
}