Given a binary tree, a target node in the binary tree, and an integer value k, find all the nodes that are at distance k from the given target node. No parent pointers are available.
Note: You have to return list in sorted order.
Example 1:
Input:
20
/ \
8 22
/ \
4 12
/ \
10 14
Target Node = 8
K = 2
Output: 10 14 22
Explanation: The three nodes at distance 2
from node 8 are 10, 14, 22.
Example 2:
Input:
20
/ \
7 24
/ \
4 3
/
1
Target Node = 7
K = 2
Output: 1 24
Your Task:
You don't need to read input or print anything. Complete the function KDistanceNodes() which takes the root of the tree, target, and K as input parameters and returns a list of nodes at k distance from target in a sorted order.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(Height of tree)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ data of node ≤ 10^{4}
1 ≤ target ≤ 10^{4}
1 ≤ k ≤ 20

见题面

见题面