(Medium) 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.
Approach 1:
- Build. hashmap of parents for every node.
- Then do BFS on this graph, each node has max 3 children (parent, child1, child2) maintain visited array with dist.
Approach 2.1:
Percolate Distance down & up in the recursion stack. (Sexy Thought).
- Keep propagating zero down until the target is found and then add+1 and keep propagating down.
- if node is not the target keep returning zero, and if node is equal to target return 1, and then onwards keep returning +1.
if the returned value is greater than zero repropagate this new value+1 down the stack again for its left and right children. But keep returning +1 to its parent.
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143886/Java-O(1)-space-excluding-recursive-stack-space.
Approach 2.2:
Good recursion here too.
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/solution/
