🔥Easy Solutions with Exaplanation in Java 📝, Python 🐍, and C++ 🖥️🧐Look at once 💻
Intuition\nWe can use DFS to traverse the tree and change the direction of edges if needed.\n\n# Approach\nFirst, we create an adjacency list to represent the t
# Intuition\nWe can use DFS to traverse the tree and change the direction of edges if needed.\n\n# Approach\nFirst, we create an adjacency list to represent the tree. Each node in the list contains a list of its neighbors.\n\nTo change the direction of edges, we assign a direction to each edge. If an edge goes from node i to node j, we represent it as i -> j. If an edge goes from node j to node i, we represent it as j -> -i.\n\nThen, we start DFS from node 0. We mark visited nodes to avoid revisiting them. If we reach a node i that has not been visited before, it means we need to change the direction of the edge that leads to node i. We do this by adding 1 to the result if the edge is directed from node j to node i (i.e., j -> i), and 0 otherwise (i.e., j -> -i).\n\nWe repeat this process until all nodes have been visited.\n\nFinally, we return the total number of edges that we have changed.\n\n# Complexity\n- Time complexity: O(n), where n is the number of nodes in the tree. We traverse the tree once using DFS.\n\n- Space complexity: O(n), where n is the number of nodes in the tree. We use a boolean array to keep track of visited nodes. Also, we use an adjacency list to represent the tree, which requires O(n) space.\n\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n![image.png](https://assets.leetcode.com/users/images/b427e686-2e5d-469a-8e7a-db5140022a6b_1677715904.0948765.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n```\n# Code\n``` Java []\nclass Solution {\n    int dfs(List<List<Integer>> al, boolean[] visited, int from) {\n        int change = 0;\n        visited[from] = true;\n        for (var to : al.get(from))\n            if (!visited[Math.abs(to)])\n                change += dfs(al, visited, Math.abs(to)) + (to > 0 ? 1 : 0);\n        return change;   \n    }\n    public int minReorder(int n, int[][] connections) {\n        List<List<Integer>> al = new ArrayList<>();\n        for(int i = 0; i < n; ++i) \n            al.add(new ArrayList<>());\n        for (var c : connections) {\n            al.get(c[0]).add(c[1]);\n            al.get(c[1]).add(-c[0]);\n        }\n        return dfs(al, new boolean[n], 0);\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    int dfs(vector<vector<int>> &al, vector<bool> &visited, int from) {\n    auto change = 0;\n    visited[from] = true;\n    for (auto to : al[from])\n        if (!visited[abs(to)])\n            change += dfs(al, visited, abs(to)) + (to > 0);\n    return change;        \n    }\n    int minReorder(int n, vector<vector<int>>& connections) {\n        vector<vector<int>> al(n);\n        for (auto &c : connections) {\n            al[c[0]].push_back(c[1]);\n            al[c[1]].push_back(-c[0]);\n        }\n        return dfs(al, vector<bool>(n) = {}, 0);\n    }\n};\n```\n``` Python []\nclass Solution:\n    def dfs(self, al, visited, from_node):\n        change = 0\n        visited[from_node] = True\n        for to_node in al[from_node]:\n            if not visited[abs(to_node)]:\n                change += self.dfs(al, visited, abs(to_node)) + (1 if to_node > 0 else 0)\n        return change\n\n    def minReorder(self, n, connections):\n        al = [[] for _ in range(n)]\n        for c in connections:\n            al[c[0]].append(c[1])\n            al[c[1]].append(-c[0])\n        visited = [False] * n\n        return self.dfs(al, visited, 0)\n\n```\n# Please Comment\uD83D\uDC4D\uD83D\uDC4D\n```\nThanks for visiting my solution comment below if you like it.\uD83D\uDE0A\n```
['Depth-First Search', 'Graph', 'Python', 'C++', 'Java']