very easy to understand c++ solution||100% faster||Manipulating the tree
Because in question it is not mention that tree should maintain its original structure so in this approach we gonna manipulate the tree structure according to u
Because in question it is not mention that tree should maintain its original structure so in this approach we gonna manipulate the tree structure according to us\n\n**There are total two casses possible **\n\n1. When root node itself target node then we simply apply dfs and match the distance of node from target and push back to vector\n\t\n\t```\n\tvoid fillVector(TreeNode* root,int val,int k,vector<int>& vec){\n        if(!root) return ;\n        if(val==k) vec.push_back(root->val);\n        solve(root->left,val+1,k,vec);\n        solve(root->right,val+1,k,vec);\n        return;\n    }\n\t```\n\t\n2.  When target node is not a root node\n\t\n\tHere first we gonna apply **fillVector** function to fill a vector so after this vector contain all possible nodes which are descendants of the target node .\n\t\n\tThen make the target\'s left child and right child NULL. Because now we don\'t need them. and now make the target node as a root of existing tree by reversing the tree with the help of this function using **backtracking**\n\t\n\t```\n\tvoid helper(TreeNode* root,TreeNode* prev,TreeNode* target,bool &valid){\n        if(!root) return;\n        \n        if(root==target){\n            valid=true;\n            target->left=prev;\n            return;\n        }\n        \n        helper(root->left,root,target,valid);\n        if(valid){\n            root->left=prev;\n            return;\n        }\n        if(!valid){\n            helper(root->right,root,target,valid);\n            if(valid){\n                root->right=prev;\n                return ;\n            }\n        }\n        return;\n    }\n\t```\n\t\n\tAfter the target node become the root node then apply **fillVector** to get other possible node \n\t\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    void fillVector(TreeNode* root,int val,int k,vector<int>& vec){\n        if(!root) return ;\n        if(val==k) vec.push_back(root->val);\n        fillVector(root->left,val+1,k,vec);\n        fillVector(root->right,val+1,k,vec);\n        return;\n    }\n    void helper(TreeNode* root,TreeNode* prev,TreeNode* target,bool &valid){\n        if(!root) return;\n        \n        if(root==target){\n            valid=true;\n            target->left=prev;\n            return;\n        }\n        \n        helper(root->left,root,target,valid);\n        if(valid){\n            root->left=prev;\n            return;\n        }\n        if(!valid){\n            helper(root->right,root,target,valid);\n            if(valid){\n                root->right=prev;\n                return ;\n            }\n        }\n        return;\n    }\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n       vector<int> vec;\n        if(k==0){\n            vec.push_back(target->val);\n            return vec;\n        }\n        fillVector(target,0,k,vec);\n        target->left=NULL;\n        target->right=NULL;\n        bool valid=false;\n        helper(root,NULL,target,valid);\n        fillVector(target,0,k,vec);\n        return vec;\n        \n    }\n};\n```\n\n  **If you like this post make sure to upvote!! Thanks**\n\t\n\t\n\t\n\t\n\n   \n
['Depth-First Search', 'Recursion']