LeetCode 863: All Nodes Distance K in Binary Tree
Problem Description
Explanation
To find all nodes at a distance k from a target node in a binary tree, we can start by performing a depth-first search (DFS) to find the path from the root to the target node. During this process, we can record the parent nodes for each node to facilitate backtracking later. Once we have found the target node, we can perform a second DFS starting from the target node to explore nodes at a distance k.
- Perform DFS to find the path from the root to the target node and record parent nodes.
- Perform a second DFS from the target node to find nodes at distance k.
Solutions
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
List<Integer> result = new ArrayList<>();
Map<TreeNode, TreeNode> parent = new HashMap<>();
Set<TreeNode> visited = new HashSet<>();
findParentNodes(root, null, parent);
findNodesAtDistanceK(target, k, parent, result, visited);
return result;
}
private void findParentNodes(TreeNode node, TreeNode parentNode, Map<TreeNode, TreeNode> parent) {
if (node == null) return;
parent.put(node, parentNode);
findParentNodes(node.left, node, parent);
findParentNodes(node.right, node, parent);
}
private void findNodesAtDistanceK(TreeNode node, int k, Map<TreeNode, TreeNode> parent, List<Integer> result, Set<TreeNode> visited) {
if (node == null || visited.contains(node)) return;
visited.add(node);
if (k == 0) {
result.add(node.val);
return;
}
findNodesAtDistanceK(node.left, k - 1, parent, result, visited);
findNodesAtDistanceK(node.right, k - 1, parent, result, visited);
findNodesAtDistanceK(parent.get(node), k - 1, parent, result, visited);
}
}Related LeetCode Problems
Loading editor...