This article is participating in Python Theme Month. See the link to the event for more details
Topic describes
This is 863 on LeetCode. All nodes of distance K in the binary tree are of medium difficulty.
Tag: “Graph theory BFS”, “Graph theory DFS”, “binary tree”
Given a binary tree (with root), a target node, and an integer value K.
Returns a list of values of all nodes with distance K from target. The answers 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:,4,1 [7] : for nodes with target distance (5) for the value of 2 nodes, value respectively, 4, 7 and 1Copy the code
Note that the input “root” and “target” are actually nodes in the tree. The above input is simply a serialized description of these objects.
Tip:
- The given tree is non-empty.
- Each node in the tree has a unique value 0 <= node.val <= 500.
- Target is the node on the tree.
- 0 <= K <= 1000.
Fundamental analysis
Obviously, if the problem is given in graph form, we can easily find the node set with distance KKK by “BFS/iterative deepening”.
Tree is a special kind of graph, we can transform binary tree into graph form, and then “BFS/iteration deepening”.
Since each point of a binary tree has at most 222 child nodes and the number of points and edges is close, it belongs to a sparse graph, so we can use the form of “adjacencies list” for storage.
The diagram building method is as follows: For the nodes (root and root.left, root and root.right) in the binary tree, an undirected edge is established.
Building a graph requires traversing the entire tree, using either DFS or BFS.
Since all the edges have a weight of 111, we can use “BFS/iteration deepen” to find a node that is KKK away from the target node target and then add it to the answer.
Some details: With each node having a unique value, we can use the node values directly to build and search.
Built figure +BFS
From the “basic analysis”, can write “build diagram + BFS” implementation.
Java code:
class Solution {
int N = 1010, M = N * 2;
int[] he = new int[N], e = new int[M], ne = new int[M];
int idx;
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
boolean[] vis = new boolean[N];
public List<Integer> distanceK(TreeNode root, TreeNode t, int k) {
List<Integer> ans = new ArrayList<>();
Arrays.fill(he, -1);
dfs(root);
Deque<Integer> d = new ArrayDeque<>();
d.addLast(t.val);
vis[t.val] = true;
while(! d.isEmpty() && k >=0) {
int size = d.size();
while (size-- > 0) {
int poll = d.pollFirst();
if (k == 0) {
ans.add(poll);
continue;
}
for (inti = he[poll]; i ! = -1 ; i = ne[i]) {
int j = e[i];
if(! vis[j]) { d.addLast(j); vis[j] =true;
}
}
}
k--;
}
return ans;
}
void dfs(TreeNode root) {
if (root == null) return;
if(root.left ! =null) {
add(root.val, root.left.val);
add(root.left.val, root.val);
dfs(root.left);
}
if(root.right ! =null) { add(root.val, root.right.val); add(root.right.val, root.val); dfs(root.right); }}}Copy the code- Time complexity: Passed
DFSThe complexity of constructing the drawing is
; throughBFSFind the distance
为
, the complexity is
. The overall complexity is
- Space complexity: O(n)O(n)O(n)
Build map + iterate deepen
From the “basic analysis”, we can write the implementation of “building diagrams + iterative deepening”.
In the form of iterative deepening, we only need to search the depth of KKK in combination with the problem idea.
Java code:
class Solution {
int N = 1010, M = N * 2;
int[] he = new int[N], e = new int[M], ne = new int[M];
int idx;
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
boolean[] vis = new boolean[N];
public List<Integer> distanceK(TreeNode root, TreeNode t, int k) {
List<Integer> ans = new ArrayList<>();
Arrays.fill(he, -1);
dfs(root);
vis[t.val] = true;
find(t.val, k, 0, ans);
return ans;
}
void find(int root, int max, int cur, List<Integer> ans) {
if (cur == max) {
ans.add(root);
return ;
}
for (inti = he[root]; i ! = -1; i = ne[i]) {
int j = e[i];
if(! vis[j]) { vis[j] =true;
find(j, max, cur + 1, ans); }}}void dfs(TreeNode root) {
if (root == null) return;
if(root.left ! =null) {
add(root.val, root.left.val);
add(root.left.val, root.val);
dfs(root.left);
}
if(root.right ! =null) { add(root.val, root.right.val); add(root.right.val, root.val); dfs(root.right); }}}Copy the code- Time complexity: Passed
DFSThe complexity of constructing the drawing is
; Find the distance by iterating deeper
为
, the complexity is
. The overall complexity is
- Space complexity: O(n)O(n)O(n)
The last
This is the No.863 article in our “Brush through LeetCode” series, which started on 2021/01/01. By the start date, there are 1916 questions on LeetCode, some of which are locked, we will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.