Leetcode/same-tree.js at master · ferrikt/Leetcode · 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
//recursive
//Time complexity : O(N),
//Space complexity: O(log(N))-best case, O(N)-worse case
var isSameTree = function(p, q) {
    if (p===null && q===null) {
        return true;
    }
    if (!(p && q)) {
        return false;
    }
    if (p.val !== q.val) {
        return false;
    }
    if (p.val === q.val) {
        return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
    }

};

//iterative
//Time complexity : O(N),
//Space complexity: O(log(N))-best case, O(N)-worse case
var isSameTree = function(p, q) {
   const check = (p,q) => {
       if (p===null && q===null) return true;
       if (!(p && q)) return false;
       return p.val === q.val;
   }

    const queueP = [];
    const queueQ = [];

    queueP.push(p);
    queueQ.push(q);

    while(queueP.length>0) {
        const elemP = queueP.shift();
        const elemQ = queueQ.shift();

        if (elemP===null && elemQ===null) {
            continue;
        }
        if (!check(elemP, elemQ)) {
            return false;
        }

        if (elemP!=null)  {
             if (!check(elemP.left, elemQ.left)) {
            return false;
        }
        else {
            queueP.push(elemP.left);
            queueQ.push(elemQ.left);
        }

        if (!check(elemP.right, elemQ.right)) {
            return false;
        }
        else {
            queueP.push(elemP.right);
            queueQ.push(elemQ.right);
        }
        }


    }
    return true;

};