dsaPractice/burningTree.java at main · sgindeed/dsaPractice · 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
class Solution
{
    static Node targetNode = null;

    public static int minTime(Node root, int target)
    {
        Map<Node, Node> parentMap = new HashMap<>();
        markParents(root, parentMap, target);
        return bfs(targetNode, parentMap);
    }

    private static void markParents(Node root, Map<Node, Node> parentMap, int target)
    {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty())
        {
            Node current = queue.poll();
            if (current.data == target)
            {
                targetNode = current;
            }
            if (current.left != null)
            {
                parentMap.put(current.left, current);
                queue.add(current.left);
            }
            if (current.right != null)
            {
                parentMap.put(current.right, current);
                queue.add(current.right);
            }
        }
    }

    private static int bfs(Node targetNode, Map<Node, Node> parentMap)
    {
        Queue<Node> queue = new LinkedList<>();
        Map<Node, Boolean> visited = new HashMap<>();

        queue.add(targetNode);
        visited.put(targetNode, true);
        int time = 0;

        while (!queue.isEmpty())
        {
            int size = queue.size();
            boolean flag = false;

            for (int i = 0; i < size; i++)
            {
                Node current = queue.poll();

                if (current.left != null && !visited.containsKey(current.left))
                {
                    flag = true;
                    visited.put(current.left, true);
                    queue.add(current.left);
                }

                if (current.right != null && !visited.containsKey(current.right))
                {
                    flag = true;
                    visited.put(current.right, true);
                    queue.add(current.right);
                }

                if (parentMap.containsKey(current) && !visited.containsKey(parentMap.get(current)))
                {
                    flag = true;
                    visited.put(parentMap.get(current), true);
                    queue.add(parentMap.get(current));
                }
            }

            if (flag)
            {
                time++;
            }
        }

        return time;
    }
}