Share My Recursive & Iterative C++ Solution


  • 0
    S
    //Solution 1 -- 0 ms 37.27%
    /**
     * 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 == NULL || q == NULL) return (p == q);
            if(p->val != q->val) return false;
            else return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    };
    
    //Solution 2 -- 3 ms 0.78%
    class Solution {
    public:
        bool isSameTree(TreeNode* p, TreeNode* q) {
            if (p == NULL || q == NULL) return (p == q);
            TreeNode* node1, *node2;
            queue<TreeNode*> q1, q2;
            q1.push(p);
            q2.push(q);
            while(!q1.empty() && !q2.empty()){
                node1 = q1.front();
                q1.pop();
                node2 = q2.front();
                q2.pop();
                if(!node1 && !node2) continue;
                if(!node1 || !node2) return false;
                if(node1->val != node2->val) return false;
                q1.push(node1->left);
                q1.push(node1->right);
                q2.push(node2->left);
                q2.push(node2->right);
            }
            return true;
        }
    };
    
    //Solution 3 -- 3 ms 0.78%
    class Solution {
    public:
        bool isSameTree(TreeNode* p, TreeNode* q) {
            if (p == NULL || q == NULL) return (p == q);
            TreeNode* node1, *node2;
            stack<TreeNode*> stk1, stk2;
            stk1.push(p);
            stk2.push(q);
            while(!stk1.empty() && !stk2.empty()){
                node1 = stk1.top();
                stk1.pop();
                node2 = stk2.top();
                stk2.pop();
                if(!node1 && !node2) continue;
                if(!node1 || !node2) return false;
                if(node1->val != node2->val) return false;
                stk1.push(node1->left);
                stk1.push(node1->right);
                stk2.push(node2->left);
                stk2.push(node2->right);
            }
            return true;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.