All Nodes Distance K in Binary Tree
Given the root of a binary tree, the value of a target node, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
Constraints:
- The number of nodes in the tree is in the range [1, 5 * 10^4].
- 1 <= Node.val <= 10^5
- Target node is a node in the tree.
- 0 <= k <= 5 * 10^4
Examples:
Input: [3,5,1,6,2,0,8,null,null,7,4], 5, 2
Output: [7,4,1]
Explanation: The nodes that are distance 2 from node 5 are nodes 7, 4, and 1.
Solutions
Depth-First Search
We use two depth-first search functions, dfs and dfs2. The dfs function checks if the current node is the target node. If it is, it calls dfs2 to find all nodes that are distance k from the target node. The dfs2 function checks if the current node is null. If it is, it returns. If the distance is 0, it adds the current node's value to the result list. Otherwise, it recursively calls itself on the left and right children of the current node, decrementing the distance by 1.
class Solution {
public: vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
vector<int> res;
dfs(root, target, k, res);
return res;
}
void dfs(TreeNode* node, TreeNode* target, int k, vector<int>& res) {
if (!node) return;
if (node == target) {
dfs2(node, k, res);
return;
}
dfs(node->left, target, k, res);
dfs(node->right, target, k, res);
}
void dfs2(TreeNode* node, int k, vector<int>& res) {
if (!node) return;
if (k == 0) {
res.push_back(node->val);
return;
}
dfs2(node->left, k - 1, res);
dfs2(node->right, k - 1, res);
}
}Follow-up:
What if the tree is not a binary tree, but a general graph?
