力扣labuladong——一刷day66

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

这道题常规的解法就是把二叉树变成一幅「图」，然后在图中用 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);
    }
}