提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
这道题常规的解法就是把二叉树变成一幅「图」，然后在图中用 BFS 算法求距离 target 节点 k 步的所有节点。
一、力扣919. 完全二叉树插入器
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class CBTInserter {
private TreeNode root;
private Deque<TreeNode> deq = new ArrayDeque<>();
public CBTInserter(TreeNode root) {
this.root = root;
Deque<TreeNode> temp = new ArrayDeque<>();
temp.offerLast(root);
while(!temp.isEmpty()){
int size = temp.size();
for(int i = 0; i < size; i ++){
TreeNode cur = temp.pollFirst();
if(cur.left != null){
temp.offerLast(cur.left);
}
if(cur.right != null){
temp.offerLast(cur.right);
}
if(cur.left == null || cur.right == null){
deq.offerLast(cur);
}
}
}
}
public int insert(int val) {
TreeNode p = new TreeNode(val);
TreeNode cur = deq.peekFirst();
if(cur.left == null){
cur.left = p;
}else{
cur.right = p;
deq.pollFirst();
}
deq.offerLast(p);
return cur.val;
}
public TreeNode get_root() {
return this.root;
}
}
/**
* Your CBTInserter object will be instantiated and called as such:
* CBTInserter obj = new CBTInserter(root);
* int param_1 = obj.insert(val);
* TreeNode param_2 = obj.get_root();
*/
二、力扣863. 二叉树中所有距离为 K 的结点
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<Integer,TreeNode> map = new HashMap<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
fun(root,null);
HashSet<Integer> visited = new HashSet<>();
List<Integer> res = new ArrayList<>();
Deque<TreeNode> deq = new ArrayDeque<>();
int len = 0;
deq.offerLast(target);
visited.add(target.val);
while(!deq.isEmpty()){
int size = deq.size();
for(int i = 0; i < size; i ++){
TreeNode temp = deq.pollFirst();
if(len == k){
res.add(temp.val);
}
TreeNode parent = map.get(temp.val);
if(parent != null && !visited.contains(parent.val)){
visited.add(parent.val);
deq.offerLast(parent);
}
if(temp.left != null && !visited.contains(temp.left.val)){
visited.add(temp.left.val);
deq.offerLast(temp.left);
}
if(temp.right != null && !visited.contains(temp.right.val)){
visited.add(temp.right.val);
deq.offerLast(temp.right);
}
}
len ++;
}
return res;
}
public void fun(TreeNode root, TreeNode parent){
if(root == null){
return;
}
map.put(root.val,parent);
fun(root.left,root);
fun(root.right,root);
}
}
