Beats 93.43%||C++ DFS using OOP inheritance
Intuition\n Describe your first thoughts on how to solve this problem. \nThe code defines a struct NodeWParent that inherits from TreeNode to add a parent point
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe code defines a struct NodeWParent that inherits from TreeNode to add a parent pointer. The Solution class converts the tree nodes to NodeWParent objects while preserving the parent pointers. It uses a depth-first search (DFS) to find nodes at a given distance k from a target node. The inheritance relationship allows the NodeWParent objects to inherit the properties of TreeNode and adds the parent member for tracking the parent node.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$O(n + k)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$O(n + k)$\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 */\nstruct NodeWParent : TreeNode {\n    NodeWParent* parent;\n    NodeWParent(int x) : TreeNode(x), parent(NULL) {}\n};\n\nclass Solution {\npublic:\n    vector<int> ans;\n    unordered_set<int> visited;\n\n    NodeWParent* start = NULL;\n\n    NodeWParent* NodeWParentReachingT(TreeNode* root, TreeNode* target) {\n        if (root == NULL)\n            return NULL;\n        NodeWParent* nodeWParent = new NodeWParent(root->val);\n\n        if (nodeWParent->val == target->val)\n            start = nodeWParent;\n\n        nodeWParent->left = NodeWParentReachingT(root->left, target);\n        if (nodeWParent->left) {\n            ((NodeWParent*)nodeWParent->left)->parent = nodeWParent;\n        }\n\n        nodeWParent->right = NodeWParentReachingT(root->right, target);\n        if (nodeWParent->right) {\n            ((NodeWParent*)nodeWParent->right)->parent = nodeWParent;\n        }\n\n        return nodeWParent;\n    }\n\n    void dfsNodeWParent(NodeWParent* start, int k) {\n        if (start == NULL || visited.count(start->val) > 0)\n            return;\n        if (k == 0)\n            ans.push_back(start->val);\n        visited.insert(start->val);\n        dfsNodeWParent(start->parent, k - 1);\n        dfsNodeWParent((NodeWParent*)start->left, k - 1);\n        dfsNodeWParent((NodeWParent*)start->right, k - 1);\n    }\n\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        NodeWParentReachingT(root, target);\n        dfsNodeWParent(start, k);\n        return ans;\n    }\n};\n\n```\n# Code with Explanation in Comments\n```\n// Definition for a binary tree node with a parent pointer\nstruct NodeWParent : TreeNode {\n    NodeWParent* parent;\n\n    //initial list and inheriting TreeNode for the NodeWParent constructor\n    NodeWParent(int x) : TreeNode(x), parent(NULL) {}\n};\n\nclass Solution {\npublic:\n    vector<int> ans;                 // Vector to store the results\n    unordered_set<int> visited;      // Set to keep track of visited nodes\n\n    NodeWParent* start = NULL;       // Pointer to the target node\'s corresponding NodeWParent object\n\n    // Function to convert the tree nodes to NodeWParent objects, while maintaining the parent pointers\n    NodeWParent* NodeWParentReachingT(TreeNode* root, TreeNode* target) {\n        if (root == NULL)\n            return NULL;\n        NodeWParent* nodeWParent = new NodeWParent(root->val);   // Create a NodeWParent object with the same value as the TreeNode\n\n        if (nodeWParent->val == target->val)                    // If the current NodeWParent object matches the target node\n            start = nodeWParent;                                // Set it as the starting node\n\n        // Recursively convert the left and right subtrees to NodeWParent objects\n        nodeWParent->left = NodeWParentReachingT(root->left, target);\n        if (nodeWParent->left) {\n            ((NodeWParent*)nodeWParent->left)->parent = nodeWParent;   // Set the parent pointer of the left child\n        }\n\n        nodeWParent->right = NodeWParentReachingT(root->right, target);\n        if (nodeWParent->right) {\n            ((NodeWParent*)nodeWParent->right)->parent = nodeWParent;  // Set the parent pointer of the right child\n        }\n\n        return nodeWParent;    // Return the NodeWParent object\n    }\n\n    // DFS function to traverse the NodeWParent tree and find nodes at a distance k\n    void dfsNodeWParent(NodeWParent* start, int k) {\n        if (start == nullptr || visited.count(start->val) > 0)\n            return;\n        if (k == 0)\n            ans.push_back(start->val);      // Add the current node\'s value to the result vector\n        visited.insert(start->val);         // Mark the current node as visited\n        dfsNodeWParent(start->parent, k - 1);    // Recursively traverse to the parent node\n        dfsNodeWParent((NodeWParent*)start->left, k - 1);   // Recursively traverse to the left child\n        dfsNodeWParent((NodeWParent*)start->right, k - 1);  // Recursively traverse to the right child\n    }\n\n    // Main function to find nodes at a distance k from the target node\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        NodeWParentReachingT(root, target);   // Convert the tree to NodeWParent objects\n        dfsNodeWParent(start, k);             // Perform DFS to find nodes at distance k\n        return ans;                           // Return the result vector\n    }\n};\n\n```\n# Code using constraint w/o unordered_set Runtime 3 ms Beats 93.43%\n```\nstruct NodeWParent : TreeNode {\n    NodeWParent* parent;\n    NodeWParent(int x) : TreeNode(x), parent(NULL) {}\n};\n\nclass Solution {\npublic:\n    vector<int> ans;\n\n    NodeWParent* start = NULL;\n\n    NodeWParent* NodeWParentReachingT(TreeNode* root, TreeNode* target) {\n        if (root == NULL)\n            return NULL;\n        NodeWParent* nodeWParent = new NodeWParent(root->val);\n\n        if (nodeWParent->val == target->val)\n            start = nodeWParent;\n\n        nodeWParent->left = NodeWParentReachingT(root->left, target);\n        if (nodeWParent->left) {\n            ((NodeWParent*)nodeWParent->left)->parent = nodeWParent;\n        }\n\n        nodeWParent->right = NodeWParentReachingT(root->right, target);\n        if (nodeWParent->right) {\n            ((NodeWParent*)nodeWParent->right)->parent = nodeWParent;\n        }\n\n        return nodeWParent;\n    }\n\n    void dfsNodeWParent(NodeWParent* start, int k) {\n        if (start == NULL || start->val==INT_MIN)\n            return;\n        if (k == 0)\n            ans.push_back(start->val);\n        start->val=INT_MIN;\n        dfsNodeWParent(start->parent, k - 1);\n        dfsNodeWParent((NodeWParent*)start->left, k - 1);\n        dfsNodeWParent((NodeWParent*)start->right, k - 1);\n    }\n\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        NodeWParentReachingT(root, target);\n        dfsNodeWParent(start, k);\n        return ans;\n    }\n};\n\n```
['Depth-First Search', 'Graph', 'C++']