0. Preface
The brushing algorithm clocked in for the sixth day and today picked up a moderate problem. But with the precipitation knowledge of the previous problem solving, it doesn't feel too painful to solve today. But there is something new to settle, so this is a record.
That's how the brushing algorithm works. It's okay in general structure, but some special cases may not always be handled in one go, so it's important to test the position after trying several times to complete all the details.
1. Problem Analysis
The structure of the tree is determined because of the hierarchy of the tree.
The first possibility is that the k-value refers to the number of layers 0+k=k from the node to its own child node.
The second possibility is that there is only one layer from the node's immediate parent, k+0=k.
The third possibility is that the number of layers from the node to the immediate parent + the number of layers from the parent sibling's child node, that is, m+n=k, 0<m<k, m, n, is an integer.
2. Problem Conversion
1. Theoretical knowledge
We find that whether 0+k=k,k+0=k, or m+n=k, we can actually unify into a third expression. So here you can use a unified function to execute known root nodes and a certain number of steps n to get the nodes that meet the criteria.
public void find(TreeNode target, int k) {
//1. Target as the root node, count when target, traverse down and count.
List<TreeNode> nodes = new ArrayList<>();
nodes.add(target);
int m = 0, current = nodes.size(), next = 0;
while (nodes.size() != 0) {
// When the count reaches k, all subsequent nodes are added and no more child nodes are added to the queue.
if (m == k) {
rnodes.addAll(nodes);
return;
}
TreeNode node = nodes.get(0);
current--;
if (node.left != null) {
next++;
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
next++;
}
nodes.remove(0);
if (current == 0) {
current = next;
next = 0;
m++;
}
}
}
2. Further sorting out problems
In the first case, we know the target node, and the number of steps n==k, so we call find(target,k) directly;
In the second case, in the third case, it is perfectly uniform to use recursive coincidence to get each direct parent node within k-steps, and then, based on the remaining number of steps, to find the other side of the parent node that satisfies n-steps.
public int getNode(TreeNode root, TreeNode target) {
if (root != null && root != target) {
if (root.left != null) {
int r = getNode(root.left, target);
if (r != -1) {
if (r + 1 == n) {
rnodes.add(root);
} else if (r + 1 < n && root.right != null) {
find(root.right, n - r - 2);
}
return r + 1;
}
}
if (root.right != null) {
int r = getNode(root.right, target);
if (r != -1) {
if (r + 1 == n) {
rnodes.add(root);
} else if (r + 1 < n && root.left != null) {
find(root.left, n - r - 2);
}
return r + 1;
}
}
}
if (root == target) {
return 0;
}
return -1;
}
3. return
//3. With the resulting sequence of nodes, the first node of the ArrayList node is saved directly, and then the other nodes are used as root s to traverse the n-tier down, as in the first case.
List<Integer> r = new ArrayList<>();
for (int i = 0; i < rnodes.size(); i++) {
r.add(rnodes.get(i).val);
}
return r;
3. Complete code and comments
package com.xhu;
import java.util.ArrayList;
import java.util.List;
public class DistanceK863 {
//Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public List<TreeNode> rnodes = new ArrayList<TreeNode>();
public int n = 0;
public void find(TreeNode target, int k) {
//1. Target as the root node, count when target, traverse down and count.
List<TreeNode> nodes = new ArrayList<>();
nodes.add(target);
int m = 0, current = nodes.size(), next = 0;
while (nodes.size() != 0) {
// When the count reaches k, all subsequent nodes are added and no more child nodes are added to the queue.
if (m == k) {
rnodes.addAll(nodes);
return;
}
TreeNode node = nodes.get(0);
current--;
if (node.left != null) {
next++;
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
next++;
}
nodes.remove(0);
if (current == 0) {
current = next;
next = 0;
m++;
}
}
}
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
/* Analytical problems
The structure of the tree has been determined. Because of the hierarchy of the tree, the first possibility is that the k-value refers to the number of layers 0+k=k from the node to its own child node.
The second possibility is that there is only one layer from the node's immediate parent, k+0=k.
The third possibility is that the number of layers from the node to the immediate parent + the number of layers from the parent sibling's child node, that is, m+n=k, 0<m<k, m, n, is an integer.
Conversion issues
We find that whether 0+k=k,k+0=k, or m+n=k, we can actually unify into a third expression.
So in the first step, the target node acts as root, gives a Tree and other roots, and finally determines the size of n.
*/
this.n = k;
find(target, k);
getNode(root, target);
//2. An ArrayList with size() k is saved from the root node to the target. When the child node is not a target yet, it will remove the first one and add it later.
//3. With the resulting sequence of nodes, the first node of the ArrayList node is saved directly, and then the other nodes are used as root s to traverse the n-tier down, as in the first case.
List<Integer> r = new ArrayList<>();
for (int i = 0; i < rnodes.size(); i++) {
r.add(rnodes.get(i).val);
}
return r;
}
public int getNode(TreeNode root, TreeNode target) {
if (root != null && root != target) {
if (root.left != null) {
int r = getNode(root.left, target);
if (r != -1) {
if (r + 1 == n) {
rnodes.add(root);
} else if (r + 1 < n && root.right != null) {
find(root.right, n - r - 2);
}
return r + 1;
}
}
if (root.right != null) {
int r = getNode(root.right, target);
if (r != -1) {
if (r + 1 == n) {
rnodes.add(root);
} else if (r + 1 < n && root.left != null) {
find(root.left, n - r - 2);
}
return r + 1;
}
}
}
if (root == target) {
return 0;
}
return -1;
}
}
4. Summary
1. Time Complexity
Because k<< n, the time complexity is O(n), and N is the number of all nodes in the tree.
2. Spatial Complexity
Since the width of the tree is much smaller than the number of nodes, the spatial complexity is O(n), n is the number of all nodes in the number.
3. Harvest
- For analysis problems, combining with the basic knowledge of the problem has been further consolidated and deepened.
- Ability to organize and categorize situations after analysis. Then borrowed functions are reused directly for the same kind of situation.
- Clear division of functions (the three functions in this topic, clear division of work, mutual cooperation), collaboration, and simplification of the work of ideas to further deepen.
- Self-created recursive reverse node finding, and have their own independent thinking on the width of the tree.