Rerooting the tree | O(N) Space | O(N) Time
Intuition\n Describe your first thoughts on how to solve this problem. \nThe answer for the subtree (nodes below the target node) can be easily calculated using
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe answer for the subtree (nodes below the target node) can be easily calculated using a simple dfs.\n\nHowever for the nodes above it, it is impossible to traverse from the target node to the root node.\nSo we reverse the links from the target node to the root node, which makes the target node the new root.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Find the answer for the subtree of target using dfs and remove the subtree by marking the left and right pointers null.\n2. Reroot the tree\n3. Repeat the dfs from target node as the remaining tree is now a subtree of target node\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N) Recursion\nO(N) For storing answer array \n\n# Code\n```\nclass Solution {\npublic:\n\n    void dfs(TreeNode* cur , int k , vector<int> &ans){\n        if(cur == nullptr) \n            return;\n        if(k == 0) {\n            ans.push_back(cur->val);\n            return;\n        }\n\n        dfs(cur->left , k - 1 , ans);\n        dfs(cur->right , k - 1 , ans);\n    }\n\n    bool reroot(TreeNode* cur , TreeNode* par , TreeNode* target){\n\n        if(cur == nullptr) return 0;\n\n        if(cur == target){\n            cur->right = par;\n            return 1;\n        }\n\n        bool left = reroot(cur->left , cur , target);\n        bool right = reroot(cur->right , cur , target);\n\n        if(left){\n            cur->left = par; \n            return 1;\n        }\n        if(right){\n            cur->right = par;\n            return 1;\n        }\n\n        return 0;\n    }\n\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        vector<int> ans;\n\n        // dfs on subtree (nodes below target node)\n        dfs(target , k , ans);\n        if(target == root or k == 0) return ans;\n\n        // reroot the tree\n        target->left = nullptr, target->right = nullptr;\n        reroot(root , nullptr , target);\n\n        // dfs on rerooted tree\n        dfs(target , k , ans);\n        return ans;\n    }\n};\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']