1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
# Leetcode 863: All Nodes Distance K in Binary Tree
---
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/
---
**Difficulty:** Medium
**Topics:** Hash Table, Tree, Depth-First Search,
Breadth-First Search, Binary Tree
## Description
Given the `root` of a binary tree, a target node `target`,
and an integer `k`, return an array of the values of all
nodes that are exactly distance `k` from the target node.
You may return the answer in any order.
## Examples
**Example 1**
ASCII diagram (target node = 5):
```
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
```
Mermaid:
```mermaid
graph TD;
A3[3] --> A5[5];
A3 --> A1[1];
A5 --> A6[6];
A5 --> A2[2];
A2 --> A7[7];
A2 --> A4[4];
A1 --> A0[0];
A1 --> A8[8];
```
Input: `root = [3,5,1,6,2,0,8,null,null,7,4]`, `target = 5`,
`k = 2`
Output: `[7, 4, 1]`
Explanation: Nodes distance 2 from the target (value 5) are
7, 4, and 1.
**Example 2**
Input: `root = [1]`, `target = 1`, `k = 3`
Output: `[]`
## Constraints
- Number of nodes is in the range `[1, 500]`.
- `0 <= Node.val <= 500`.
- All `Node.val` values are unique.
- `target` is the value of one of the nodes in the tree.
- `0 <= k <= 1000`.
---
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
}
};
```
```py
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
pass
```
---
# Solutions
**@p13i**:
It is trivial to find the nodes that are `k` levels below a
node: e.g., BFS for `k` levels.
To find nodes that are `k` levels above a node, we can use a
space-limited stack-like structure that will keep a record
of the `k` parents of the current node as we search for the
`target` node under the `root`.
After finding the target, we can do a BFS in three
directions:
1. left child
2. right child
3. parent
To faciliate the lookup from a node to its parent, we can
use our lookup stack. The space needed will be:
$$ O( k ) $$
to maintain a parent `lookup` structure and similar order
for performing a BFS(?). The time needed will be dependent
on `k` and how long it will take to find the `target`, as
much as:
$$ O( n ) $$
for `n` nodes in the tree.
The pseudo-code for such an algorithm is:
1. Find the `k`-th parent of `target` and build a
child-to-parent lookup structure.
2. Perform a three-way breadth-first-search until saving the
`k`-th row.
3. Return the `k`-th row of this BFS as the resultant list.