Logic-Building-/Same Tree.cpp at main · TanviMahajan11/Logic-Building- · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {


        // Approrach 1 - level order traversal

        if( p == nullptr && q == nullptr)
            return true;

        if( p == nullptr || q == nullptr)
            return false;

        queue <TreeNode*> q1;
        queue <TreeNode*> q2;

        q1.push(p);
        q2.push(q);

        while( !q1.empty() && !q2.empty())
        {
            TreeNode* front1 = q1.front();
            q1.pop();

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

            if(front1->val != front2->val )
                return false;

            if (
               ( front1->left == nullptr && front2->left != nullptr ) ||
            ( front1->left != nullptr && front2->left == nullptr ))
                return false;

             if (
               ( front1->right == nullptr && front2->right != nullptr ) ||
            ( front1->right != nullptr && front2->right == nullptr ))
                return false;


            if( front1->left != nullptr)
                q1.push(front1->left);
            if( front1->right != nullptr)
                q1.push(front1->right);

            if( front2->left != nullptr)
                q2.push(front2->left);
             if( front2->right != nullptr)
                q2.push(front2->right);

        }

        return true;

        // Approcch - 2

        // if both nodes nullptr return true
        if(p == nullptr && q == nullptr)
            return true;

        // check if any of the node is null
        if(p == nullptr || q == nullptr)
            return false;

        return (
            p->val == q->val
            &&
            isSameTree(p->left, q->left)
            &&
            isSameTree(p->right, q->right)
        );
    }
};