863. All Nodes Distance K in Binary Tree LeetCode Solution
In this guide, you will get 863. All Nodes Distance K in Binary Tree LeetCode Solution with the best time and space complexity. The solution to All Nodes Distance K in Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of All Nodes Distance K in Binary Tree
Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
You can return the answer in any order.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
Example 2:
Input: root = [1], target = 1, k = 3
Output: []
Constraints:
The number of nodes in the tree is in the range [1, 500].
0 <= Node.val <= 500
All the values Node.val are unique.
target is the value of one of the nodes in the tree.
0 <= k <= 1000
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
863. All Nodes Distance K in Binary Tree LeetCode Solution in C++
class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
vector<int> ans;
unordered_map<TreeNode*, int> nodeToDist; // {node: distance to target}
getDists(root, target, nodeToDist);
dfs(root, k, 0, nodeToDist, ans);
return ans;
}
private:
void getDists(TreeNode* root, TreeNode* target,
unordered_map<TreeNode*, int>& nodeToDist) {
if (root == nullptr)
return;
if (root == target) {
nodeToDist[root] = 0;
return;
}
getDists(root->left, target, nodeToDist);
if (const auto it = nodeToDist.find(root->left); it != nodeToDist.cend()) {
// The target is in the left subtree.
nodeToDist[root] = it->second + 1;
return;
}
getDists(root->right, target, nodeToDist);
if (const auto it = nodeToDist.find(root->right); it != nodeToDist.cend())
// The target is in the right subtree.
nodeToDist[root] = it->second + 1;
}
void dfs(TreeNode* root, int k, int dist,
unordered_map<TreeNode*, int>& nodeToDist, vector<int>& ans) {
if (root == nullptr)
return;
if (const auto it = nodeToDist.find(root); it != nodeToDist.cend())
dist = it->second;
if (dist == k)
ans.push_back(root->val);
dfs(root->left, k, dist + 1, nodeToDist, ans);
dfs(root->right, k, dist + 1, nodeToDist, ans);
}
}; /* code provided by PROGIEZ */
863. All Nodes Distance K in Binary Tree LeetCode Solution in Java
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
List<Integer> ans = new ArrayList<>();
Map<TreeNode, Integer> nodeToDist = new HashMap<>(); // {node: distance to target}
getDists(root, target, nodeToDist);
dfs(root, k, 0, nodeToDist, ans);
return ans;
}
private void getDists(TreeNode root, TreeNode target, Map<TreeNode, Integer> nodeToDist) {
if (root == null)
return;
if (root == target) {
nodeToDist.put(root, 0);
return;
}
getDists(root.left, target, nodeToDist);
if (nodeToDist.containsKey(root.left)) {
// The target is in the left subtree.
nodeToDist.put(root, nodeToDist.get(root.left) + 1);
return;
}
getDists(root.right, target, nodeToDist);
if (nodeToDist.containsKey(root.right))
// The target is in the right subtree.
nodeToDist.put(root, nodeToDist.get(root.right) + 1);
}
private void dfs(TreeNode root, int k, int dist, Map<TreeNode, Integer> nodeToDist,
List<Integer> ans) {
if (root == null)
return;
if (nodeToDist.containsKey(root))
dist = nodeToDist.get(root);
if (dist == k)
ans.add(root.val);
dfs(root.left, k, dist + 1, nodeToDist, ans);
dfs(root.right, k, dist + 1, nodeToDist, ans);
}
} // code provided by PROGIEZ
863. All Nodes Distance K in Binary Tree LeetCode Solution in Python
