# 2458. Height of Binary Tree After Subtree Removal Queries
###### tags: `Leetcode` `Hard` `DFS` `BFS`
Link: https://leetcode.com/problems/height-of-binary-tree-after-subtree-removal-queries/description/
## 思路
一开始的思路是层序遍历每层都几个node
然后记录每个node的children node都在哪一层 每一层有几个
因此每次删掉一个node的时候我们就需要从最深一层开始找 看是不是删掉当前node会把这一层的node都删掉 我们找到最下面的还有node的一层就是答案
但是上述方法会TLE(code在下面)

正确思路参考[这里](https://leetcode.com/problems/height-of-binary-tree-after-subtree-removal-queries/solutions/2757990/python-3-explanation-with-pictures-dfs/)
每个node都有```depth```和```height```, pass这个node的最长路径的长度就是```depth+height```
我们找到每一层的所有node 并用priority queue按照height排序
每次删掉一个node我们找到这层里面height最大的node 如果刚好就要删掉这个node 那么我们就找第二大的height 第二大的height+当前的depth就是答案
如果不用删掉height最大的node 那么最大的height+当前的depth就是答案

## Code

class Solution {
    public int[] treeQueries(TreeNode root, int[] queries) {
        Map<Integer, Integer> depth = new HashMap<>();
        Map<Integer, Integer> height = new HashMap<>();
        dfs(root, depth, height, 0);
        Map<Integer, Queue<Integer>> cousins = new HashMap<>();
        for(int val:depth.keySet()){
            int d = depth.get(val);
            if(!cousins.containsKey(d)) cousins.put(d, new PriorityQueue<>((a,b)->(height.get(b)-height.get(a))));
            cousins.get(d).add(val);
        }
        int[] ans = new int[queries.length];
        for(int i=0; i<queries.length; i++){
            int val = queries[i];
            int d = depth.get(val);
            if(cousins.get(d).size()==1) ans[i] = d-1;
            else if(cousins.get(d).peek()!=val){
                ans[i] = d+height.get(cousins.get(d).peek());
            }
            else{
                cousins.get(d).poll();
                ans[i] = d+height.get(cousins.get(d).peek());
                cousins.get(d).add(val);
            }
        }
        return ans;
    }
    public void dfs(TreeNode root, Map<Integer, Integer> depth, Map<Integer, Integer> height, int d){
        depth.put(root.val, d);
        if(root.left!=null) dfs(root.left, depth, height, d+1);
        if(root.right!=null) dfs(root.right, depth, height, d+1);
        if(root.left==null && root.right==null) height.put(root.val, 0);
        else height.put(root.val, Math.max(root.left==null?0:height.get(root.left.val), root.right==null?0:height.get(root.right.val))+1);
    }
}