C# Solution for All Nodes Distance K in Binary Tree Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind the solution is to use a depth-first search (DFS) approach to trav
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind the solution is to use a depth-first search (DFS) approach to traverse the binary tree and find all nodes that are at a distance k from the target node.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe approach consists of two main steps:\n\nBuild Parent Map: First, we build a parent map that stores the parent node for each node in the binary tree. This map is used to navigate towards the root during the DFS traversal.\n\nDFS Traversal: Starting from the target node, we perform a DFS to explore its children, parent nodes, and siblings. We keep track of the visited nodes to avoid revisiting them. If the distance k is reached during the traversal, we add the node\'s value to the result list.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe time complexity of the solution is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the DFS traversal. \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is also O(N) as we use additional space to store the parent map and the visited set.\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int x) { val = x; }\n * }\n */\npublic class Solution \n{\n    private Dictionary<TreeNode, TreeNode> parentMap;\n    public IList<int> DistanceK(TreeNode root, TreeNode target, int k) \n    {\n        parentMap = new Dictionary<TreeNode, TreeNode>();\n        BuildParentMap(root, null);\n\n        List<int> result = new List<int>();\n        HashSet<TreeNode> visited = new HashSet<TreeNode>();\n\n        DFS(target, k, visited, result);\n\n        return result;\n    }\n    private void BuildParentMap(TreeNode node, TreeNode parent) \n    {\n        if (node == null) return;\n        parentMap[node] = parent;\n        BuildParentMap(node.left, node);\n        BuildParentMap(node.right, node);\n    }\n    private void DFS(TreeNode node, int k, HashSet<TreeNode> visited, List<int> result) \n    {\n        if (node == null || visited.Contains(node)) return;\n\n        visited.Add(node);\n\n        if (k == 0) {\n            result.Add(node.val);\n            return;\n        }\n\n        if (node.left != null) DFS(node.left, k - 1, visited, result);\n        if (node.right != null) DFS(node.right, k - 1, visited, result);\n\n        TreeNode parent;\n        if (parentMap.TryGetValue(node, out parent))\n            DFS(parent, k - 1, visited, result);\n    }\n\n}\n```
['C#']