https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
We are given a binary tree (with root node
root
), a target
node, and an integer value K
.
Return a list of the values of all nodes that have a distance
K
from the target
node. The answer can be returned 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. Note that the inputs "root" and "target" are actually TreeNodes. The descriptions of the inputs above are just serializations of these objects.
X. https://www.geeksforgeeks.org/print-nodes-distance-k-given-node-binary-tree/
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143752/JAVA-Graph-%2B-BFS
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143729/Python-DFS-and-BFS
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143713/Easy-to-understand-Graph-DFS
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/163101/Java-Solution
From
There are two types of nodes to be considered.
1) Nodes in the subtree rooted with target node. For example if the target node is 8 and k is 2, then such nodes are 10 and 14.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 8 and k is 2, the node 22 comes in this category.
1) Nodes in the subtree rooted with target node. For example if the target node is 8 and k is 2, then such nodes are 10 and 14.
2) Other nodes, may be an ancestor of target, or a node in some other subtree. For target node 8 and k is 2, the node 22 comes in this category.
Finding the first type of nodes is easy to implement. Just traverse subtrees rooted with the target node and decrement k in recursive call. When the k becomes 0, print the node currently being traversed (See this for more details). Here we call the function as printkdistanceNodeDown().
How to find nodes of second type? For the output nodes not lying in the subtree with the target node as the root, we must go through all ancestors. For every ancestor, we find its distance from target node, let the distance be d, now we go to other subtree (if target was found in left subtree, then we go to right subtree and vice versa) of the ancestor and find all nodes at k-d distance from the ancestor.
List<Integer> ans;
TreeNode target;
int K;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
ans = new LinkedList();
this.target = target;
this.K = K;
dfs(root);
return ans;
}
// Return vertex distance from node to target if exists, else -1
// Vertex distance: the number of vertices on the path from node to target
public int dfs(TreeNode node) {
if (node == null)
return -1;
else if (node == target) {
subtree_add(node, 0);
return 1;
} else {
int L = dfs(node.left), R = dfs(node.right);
if (L != -1) {
if (L == K)
ans.add(node.val);
subtree_add(node.right, L + 1);
return L + 1;
} else if (R != -1) {
if (R == K)
ans.add(node.val);
subtree_add(node.left, R + 1);
return R + 1;
} else {
return -1;
}
}
}
// Add all nodes 'K - dist' from the node to answer.
public void subtree_add(TreeNode node, int dist) {
if (node == null)
return;
if (dist == K)
ans.add(node.val);
else {
subtree_add(node.left, dist + 1);
subtree_add(node.right, dist + 1);
}
}
X. Graph BFShttps://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143752/JAVA-Graph-%2B-BFS
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143729/Python-DFS-and-BFS
A recursive dfs funciton
The key of map is node's val and the value of map is node's connected nodes' vals.
Then we do N times bfs search loop to find all nodes of distance
connect
help to build up a map conn
.The key of map is node's val and the value of map is node's connected nodes' vals.
Then we do N times bfs search loop to find all nodes of distance
K
//Method 1: use HashMap
//1. build a undirected graph using treenodes as vertices, and the parent-child relation as edges
//2. do BFS with source vertice (target) to find all vertices with distance K to it.
class Solution {
Map<TreeNode, List<TreeNode>> map = new HashMap();
//here can also use Map<TreeNode, TreeNode> to only store the child - parent mapping, since parent-child mapping is inherent in the tree structure
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> res = new ArrayList<Integer> ();
if (root == null || K < 0) return res;
buildMap(root, null);
if (!map.containsKey(target)) return res;
Set<TreeNode> visited = new HashSet<TreeNode>();
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(target);
visited.add(target);
while (!q.isEmpty()) {
int size = q.size();
if (K == 0) {
for (int i = 0; i < size ; i++) res.add(q.poll().val);
return res;
}
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
for (TreeNode next : map.get(node)) {
if (visited.contains(next)) continue;
visited.add(next);
q.add(next);
}
}
K--;
}
return res;
}
private void buildMap(TreeNode node, TreeNode parent) {
if (node == null) return;
if (!map.containsKey(node)) {
map.put(node, new ArrayList<TreeNode>());
if (parent != null) { map.get(node).add(parent); map.get(parent).add(node) ; }
buildMap(node.left, node);
buildMap(node.right, node);
}
}
}
//Method 2: No HashMap
//kind of like clone the tree, in the meanwhile add a parent link to the node
class Solution {
private GNode targetGNode;
private class GNode {
TreeNode node;
GNode parent, left, right;
GNode (TreeNode node) {
this.node = node;
}
}
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> res = new ArrayList<Integer> ();
if (root == null || K < 0) return res;
cloneGraph(root, null, target);
if (targetGNode == null) return res;
Set<GNode> visited = new HashSet<GNode>();
Queue<GNode> q = new LinkedList<GNode>();
q.add(targetGNode);
visited.add(targetGNode);
while (!q.isEmpty()) {
int size = q.size();
if (K == 0) {
for (int i = 0; i < size ; i++) res.add(q.poll().node.val);
return res;
}
for (int i = 0; i < size; i++) {
GNode gNode = q.poll();
if (gNode.left != null && !visited.contains(gNode.left)) { visited.add(gNode.left); q.add(gNode.left); }
if (gNode.right != null && !visited.contains(gNode.right)) { visited.add(gNode.right); q.add(gNode.right); }
if (gNode.parent != null && !visited.contains(gNode.parent)) { visited.add(gNode.parent); q.add(gNode.parent); }
}
K--;
}
return res;
}
private GNode cloneGraph(TreeNode node, GNode parent, TreeNode target) {
if (node == null) return null;
GNode gNode = new GNode(node);
if (node == target) targetGNode = gNode;
gNode.parent = parent;
gNode.left = cloneGraph(node.left, gNode, target);
gNode.right = cloneGraph(node.right, gNode, target);
return gNode;
}
}
X. DFShttps://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143713/Easy-to-understand-Graph-DFS
It would be very easy to find the neighbors in K distance in a graph, so I converted the tree into a graph whose node(GNode) has neighbors, which include it’s parent and left & right children:
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143775/very-easy-to-understand-c%2B%2B-solution.- Using recursion to find all of the son=>parent pair into a map.
- Using dfs to find K distance node, visited nodes will be recorded.
vector<int> ans;
map<TreeNode*, TreeNode*> parent; // son=>parent
set<TreeNode*> visit; //record visied node
void findParent(TreeNode* node){
if(!node ) return;
if( node->left ){
parent[node->left] = node;
findParent(node->left);
}
if( node->right){
parent[node->right] = node;
findParent(node->right);
}
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
if( !root ) return {};
findParent(root);
dfs(target, K );
return ans;
}
void dfs( TreeNode* node, int K){
if( visit.find(node) != visit.end() )
return;
visit.insert(node);
if( K == 0 ){
ans.push_back(node->val);
return;
}
if( node->left ){
dfs(node->left, K-1);
}
if( node->right){
dfs(node->right, K-1);
}
TreeNode* p = parent[node];
if( p )
dfs(p, K-1);
}
As we know, if the distance from a node to target node is
k
, the distance from its child to the target node is k + 1
unless the child node is closer to the target node which means the target node is in it's subtree.
To avoid this situation, we need to travel the tree first to find the path from
root
to target
, to:- store the value of distance in hashamp from the
all nodes in that path
totarget
Then we can easily use dfs to travel the whole tree. Every time when we meet a treenode which has already stored in map, use the stored value in hashmap instead of the value from its parent node.
Great solution, but both helper method has one parameter never used.
Keeping the distance from parents node to the target node is so brilliant!!!
the most brilliant part is to update the length and do the check then pass the length + 1 to next level in dfs function
- Note the distances from target node to all the nodes up the path to root from target in a map.
- Apply pre-order traversal using the map above.
- If the node is present in the map, use that distance
- else assume
d+1
where d = distance for the parent.
Map<TreeNode, Integer> map = new HashMap<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> res = new LinkedList<>();
find(root, target);
dfs(root, target, K, map.get(root), res);
return res;
}
// find target node first and store the distance in that path that we could use it later directly
private int find(TreeNode root, TreeNode target) {
if (root == null) return -1;
if (root == target) {
map.put(root, 0);
return 0;
}
int left = find(root.left, target);
if (left >= 0) {
map.put(root, left + 1);
return left + 1;
}
int right = find(root.right, target);
if (right >= 0) {
map.put(root, right + 1);
return right + 1;
}
return -1;
}
private void dfs(TreeNode root, TreeNode target, int K, int length, List<Integer> res) {
if (root == null) return;
if (map.containsKey(root)) length = map.get(root);
if (length == K) res.add(root.val);
dfs(root.left, target, K, length + 1, res);
dfs(root.right, target, K, length + 1, res);
}
https://leetcode.com/articles/all-nodes-distance-k-in-binary-tree/From
root
, say the target
node is at depth 3
in the left branch. It means that any nodes that are distance K - 3
in the right branch should be added to the answer.
Algorithm
Traverse every
node
with a depth first search dfs
. We'll add all nodes x
to the answer such that node
is the node on the path from x
to target
that is closest to the root
.
To help us,
dfs(node)
will return the distance from node
to the target
. Then, there are 4 cases:- If
node == target
, then we should add nodes that are distanceK
in the subtree rooted attarget
. - If
target
is in the left branch ofnode
, say at distanceL+1
, then we should look for nodes that are distanceK - L - 1
in the right branch. - If
target
is in the right branch ofnode
, the algorithm proceeds similarly. - If
target
isn't in either branch ofnode
, then we stop.
In the above algorithm, we make use of the auxillary function
subtree_add(node, dist)
which adds the nodes in the subtree rooted at node
that are distance K - dist
from the given node
.- Time Complexity: , where is the number of nodes in the given tree.
- Space Complexity: .
List<Integer> ans;
TreeNode target;
int K;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
ans = new LinkedList();
this.target = target;
this.K = K;
dfs(root);
return ans;
}
// Return distance from node to target if exists, else -1
public int dfs(TreeNode node) {
if (node == null)
return -1;
else if (node == target) {
subtree_add(node, 0);
return 1;
} else {
int L = dfs(node.left), R = dfs(node.right);
if (L != -1) {
if (L == K) ans.add(node.val);
subtree_add(node.right, L + 1);
return L + 1;
} else if (R != -1) {
if (R == K) ans.add(node.val);
subtree_add(node.left, R + 1);
return R + 1;
} else {
return -1;
}
}
}
// Add all nodes 'K - dist' from the node to answer.
public void subtree_add(TreeNode node, int dist) {
if (node == null) return;
if (dist == K)
ans.add(node.val);
else {
subtree_add(node.left, dist + 1);
subtree_add(node.right, dist + 1);
}
}
X.
https://leetcode.com/problems/all-nodes-distance-k-in-binary-t
ree/discuss/143798/1ms-beat-100-simple-Java-dfs-using-hashmap-with-explanation
https://leetcode.com/problems/all-nodes-distance-k-in-binary-t
ree/discuss/143798/1ms-beat-100-simple-Java-dfs-using-hashmap-with-explanation
As we know, if the distance from a node to target node is
k
, the distance from its child to the target node is k + 1
unless the child node is closer to the target node which means the target node is in it's subtree.
To avoid this situation, we need to travel the tree first to find the path from
root
to target
, to:- store the value of distance in hashamp from the
all nodes in that path
totarget
Then we can easily use dfs to travel the whole tree. Every time when we meet a treenode which has already stored in map, use the stored value in hashmap instead of the value from its parent node.
If we know the parent of every node
x
, we know all nodes that are distance 1
from x
. We can then perform a breadth first search from the target
node to find the answer.
Algorithm
We first do a depth first search where we annotate every node with information about it's parent.
After, we do a breadth first search to find all nodes a distance
K
from the target
.- Time Complexity: , where is the number of nodes in the given tree.
Map<TreeNode,TreeNode> parent;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
parent = new HashMap();
dfs(root, null);
Queue<TreeNode> queue = new LinkedList();
queue.add(null);
queue.add(target);
Set<TreeNode> seen = new HashSet();
seen.add(target);
seen.add(null);
int dist = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
if (dist == K) {
List<Integer> ans = new ArrayList();
for (TreeNode n : queue)
ans.add(n.val);
return ans;
}
queue.offer(null);
dist++;
} else {
if (!seen.contains(node.left)) {
seen.add(node.left);
queue.offer(node.left);
}
if (!seen.contains(node.right)) {
seen.add(node.right);
queue.offer(node.right);
}
TreeNode par = parent.get(node);
if (!seen.contains(par)) {
seen.add(par);
queue.offer(par);
}
}
}
return new ArrayList<Integer>();
}
public void dfs(TreeNode node, TreeNode par) {
if (node != null) {
parent.put(node, par);
dfs(node.left, node);
dfs(node.right, node);
}
}
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143886/Java-O(1)-space-excluding-recursive-stack-space
https://leetcode.com/articles/all-nodes-distance-k-in-binary-tree/
https://leetcode.com/articles/all-nodes-distance-k-in-binary-tree/
If we know the parent of every node
x
, we know all nodes that are distance 1
from x
. We can then perform a breadth first search from the target
node to find the answer.
Algorithm
We first do a depth first search where we annotate every node with information about it's parent.
After, we do a breadth first search to find all nodes a distance
K
from the target
.- Time Complexity: , where is the number of nodes in the given tree.
- Space Complexity: .
Map<TreeNode, TreeNode> parent;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
parent = new HashMap();
dfs(root, null);
Queue<TreeNode> queue = new LinkedList();
queue.add(null);
queue.add(target);
Set<TreeNode> seen = new HashSet();
seen.add(target);
seen.add(null);
int dist = 0;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
if (dist == K) {
List<Integer> ans = new ArrayList();
for (TreeNode n : queue)
ans.add(n.val);
return ans;
}
queue.offer(null);
dist++;
} else {
if (!seen.contains(node.left)) {
seen.add(node.left);
queue.offer(node.left);
}
if (!seen.contains(node.right)) {
seen.add(node.right);
queue.offer(node.right);
}
TreeNode par = parent.get(node);
if (!seen.contains(par)) {
seen.add(par);
queue.offer(par);
}
}
}
return new ArrayList<Integer>();
}
public void dfs(TreeNode node, TreeNode par) {
if (node != null) {
parent.put(node, par);
dfs(node.left, node);
dfs(node.right, node);
}
}
X. Approach 2: Percolate Distance
TODO https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143886/Java-O(1)-space-excluding-recursive-stack-space
From
root
, say the target
node is at depth 3
in the left branch. It means that any nodes that are distance K - 3
in the right branch should be added to the answer.
Algorithm
Traverse every
node
with a depth first search dfs
. We'll add all nodes x
to the answer such that node
is the node on the path from x
to target
that is closest to the root
.
To help us,
dfs(node)
will return the distance from node
to the target
. Then, there are 4 cases:- If
node == target
, then we should add nodes that are distanceK
in the subtree rooted attarget
. - If
target
is in the left branch ofnode
, say at distanceL+1
, then we should look for nodes that are distanceK - L - 1
in the right branch. - If
target
is in the right branch ofnode
, the algorithm proceeds similarly. - If
target
isn't in either branch ofnode
, then we stop.
In the above algorithm, we make use of the auxillary function
subtree_add(node, dist)
which adds the nodes in the subtree rooted at node
that are distance K - dist
from the given node
.
Time Complexity: , where is the number of nodes in the given tree.
List<Integer> ans;
TreeNode target;
int K;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
ans = new LinkedList<>();
this.target = target;
this.K = K;
dfs(root);
return ans;
}
// Return vertex distance from node to target if exists, else -1
// Vertex distance: the number of vertices on the path from node to target
public int dfs(TreeNode node) {
if (node == null)
return -1;
else if (node == target) {
subtree_add(node, 0);
return 1;
} else {
int L = dfs(node.left), R = dfs(node.right);
if (L != -1) {
if (L == K)
ans.add(node.val);
subtree_add(node.right, L + 1);
return L + 1;
} else if (R != -1) {
if (R == K)
ans.add(node.val);
subtree_add(node.left, R + 1);
return R + 1;
} else {
return -1;
}
}
}
// Add all nodes 'K - dist' from the node to answer.
public void subtree_add(TreeNode node, int dist) {
if (node == null)
return;
if (dist == K)
ans.add(node.val);
else {
subtree_add(node.left, dist + 1);
subtree_add(node.right, dist + 1);
}
}
TODO https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143886/Java-O(1)-space-excluding-recursive-stack-space