✔✔ Simple DFS Solution || Beats 100% || Readable Code
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe main intuition behind this problem is that the K distance node could be up the tr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe main intuition behind this problem is that the K distance node could be up the tree as well as left or right of the target node.\n\nSo for traversing up the tree we can store the parent of each node in a map with a simple DFS.\n\nAfter which we can just call the function findNodes in the following manner:\n\n\nfindNodes(origin,k) -> returns a vector of all the nodes which are at distance k from the origin.\n\nNow, All I need to do is to find the nodes with which are at distance k-1 from the parent, the left child and the right child.\n\nNote: We also need to keep track of the visited nodes as the findNode could just go up and then down again and again until k = 0 and return \nwrong answers.\n\nWe can also make the parentMap as unordered_map<int,TreeNode*> instead of unordered_map<TreeNode*,TreeNode*> as the \nvalues are unique.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n */\nclass Solution {\npublic:\n\n    unordered_map<TreeNode*,TreeNode*> parentMap;\n    void dfs(TreeNode* root,TreeNode *parent){\n        if(root==NULL) return;\n\n        parentMap[root] = parent;\n        dfs(root->left,root);\n        dfs(root->right,root);\n\n        return;\n    }\n\n    unordered_map<TreeNode*,bool> vis;\n\n    vector<int> findNodes(TreeNode* origin,int distance){\n\n        if(origin==NULL){\n            return vector<int>();\n        }\n\n        if(vis[origin]==true) return vector<int>();\n\n        if(distance == 0){\n            return vector<int>(1,origin->val);\n        }\n\n        vis[origin]=true;\n        \n        vector<int> res1 = findNodes(origin->left,distance-1);\n        vector<int> res2 = findNodes(origin->right,distance-1);\n        vector<int> res3 = findNodes(parentMap[origin],distance-1);\n\n        res1.insert(res1.end(),res2.begin(),res2.end());\n        res1.insert(res1.end(),res3.begin(),res3.end());\n\n        return res1;\n\n\n    }\n\n\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        dfs(root,NULL);\n        return findNodes(target,k);\n    }\n};\n```
['Hash Table', 'Depth-First Search', 'Recursion', 'C++']