LeetCode-Solutions/Algorithms/Tree/LeafSimilar.java at master · architsingla13/LeetCode-Solutions · 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package Tree;

import java.util.Stack;

/**
 Author - archit.s
 Date - 18/08/18
 Time - 4:45 PM
 */

public class LeafSimilar {

    // Solution 1

    /*private void insertRemoveLeafStack(TreeNode r, ArrayList<Integer> s, boolean add, AtomicInteger index){
        if(r == null || index.intValue() == -1){
            return;
        }
        if(r.left == null && r.right == null){
            if(add){
                s.add(index.intValue(), r.val);
                index.incrementAndGet();
            }
            else{
                if(r.val == s.get(index.intValue())){
                    s.set(index.intValue(), 0);
                    index.incrementAndGet();
                }
                else{
                    index.set(-1);
                }
            }
        }
        else{
            insertRemoveLeafStack(r.left, s, add, index);
            insertRemoveLeafStack(r.right, s, add, index);
        }
    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        ArrayList<Integer> s = new ArrayList<>();

        if(root1 == null && root2 != null){
            return false;
        }
        if(root2 == null && root1 != null){
            return false;
        }

        AtomicInteger i = new AtomicInteger(0);
        insertRemoveLeafStack(root1, s, true, i);
        i = new AtomicInteger(0);
        insertRemoveLeafStack(root2, s, false, i);

        boolean flag = true;
        for (Integer value : s) {
            if (value != 0) {
                flag = false;
                break;
            }
        }
        return flag;
    }*/

    private int dfs(Stack<TreeNode> s){

        while (true){

            final TreeNode pop = s.pop();

            if(pop.left != null){
                s.push(pop.left);
            }
            if(pop.right != null){
                s.push(pop.right);
            }
            if(pop.left == null && pop.right == null){
                return pop.val;
            }
        }
    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();

        if(root1 != null){
            s1.push(root1);
        }
        if(root2 != null){
            s2.push(root2);
        }

        while (!s1.empty() && !s2.empty()){
            if(dfs(s1) != dfs(s2)){
                return false;
            }
        }

        return s1.empty() && s2.empty();

    }
}