Leetcode 2458. 移除子樹後的二叉樹高度

給你一棵 二叉樹 的根節點 root ，樹中有 n 個節點。每個節點都可以被配置設定一個從 1 到 n 且互不相同的值。另給你一個長度為 m 的數組 queries 。

你必須在樹上執行 m 個 獨立 的查詢，其中第 i 個查詢你需要執行以下操作：

    從樹中 移除 以 queries[i] 的值作為根節點的子樹。題目所用測試用例保證 queries[i] 不 等于根節點的值。

傳回一個長度為 m 的數組 answer ，其中 answer[i] 是執行第 i 個查詢後樹的高度。

注意：

    查詢之間是獨立的，是以在每個查詢執行後，樹會回到其 初始 狀态。
    樹的高度是從根到樹中某個節點的 最長簡單路徑中的邊數 。

 

示例 1：

輸入：root = [1,3,4,2,null,6,5,null,null,null,null,null,7], queries = [4]
輸出：[2]
解釋：上圖展示了從樹中移除以 4 為根節點的子樹。
樹的高度是 2（路徑為 1 -> 3 -> 2）。

示例 2：

輸入：root = [5,8,9,2,1,3,7,4,6], queries = [3,2,4,8]
輸出：[3,2,3,2]
解釋：執行下述查詢：
- 移除以 3 為根節點的子樹。樹的高度變為 3（路徑為 5 -> 8 -> 2 -> 4）。
- 移除以 2 為根節點的子樹。樹的高度變為 2（路徑為 5 -> 8 -> 1）。
- 移除以 4 為根節點的子樹。樹的高度變為 3（路徑為 5 -> 8 -> 2 -> 6）。
- 移除以 8 為根節點的子樹。樹的高度變為 2（路徑為 5 -> 9 -> 3）。

 

提示：

    樹中節點的數目是 n
    2 <= n <= 105
    1 <= Node.val <= n
    樹中的所有值 互不相同
    m == queries.length
    1 <= m <= min(n, 104)
    1 <= queries[i] <= n
    queries[i] != root.val      

• 首先統計出所有子樹的高度。然後再計算出移除每一個結點後樹的高度變化，對于某一層來說，具有高度最大和次大的結點，當移除非高度最大的節點時，樹的最大高度不會改變，為這一層節點最大高度+根節點到該層的路徑邊數；當移除最大高度時，樹的最大高度變為次大高度+根節點到該層的路徑邊數。當一層隻有一個節點時，根節點到該層的路徑數要-1。
• 時間複雜度：
• 空間複雜度：

class Solution {
    Map<Integer, Integer> height = new HashMap<>();
    Map<Integer, Integer> valToAns = new HashMap<>();
    public int[] treeQueries(TreeNode root, int[] queries) {
        int n = queries.length;
        int[] ans = new int[n];
        getLength(root); 
        Queue<TreeNode> q = new LinkedList<>();
        List<Integer> vals = new ArrayList<>();
        q.add(root);  
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            int maxv = 0, maxv2 = -1;
            for (int i = 1; i <= size; i++) {
                TreeNode p = q.poll();
                vals.add(p.val);
                if (height.get(p.val) > maxv) {
                    maxv2 = maxv;
                    maxv = height.get(p.val);
                } else if (height.get(p.val) > maxv2) {
                    maxv2 = height.get(p.val);
                }
                if (p.left != null) q.add(p.left); 
                if (p.right != null) q.add(p.right);
            }
            for (int i = 0; i < size; i++){
                int val = vals.get(i);
                if (height.get(val) == maxv) valToAns.put(val, maxv2 + step);
                else valToAns.put(val, maxv + step);
                if (size == 1) valToAns.put(val, valToAns.get(val) - 1); //特殊情況
            }
            vals.clear();
            step++;
        } 
        for (int i = 0; i < n; i++) ans[i] = valToAns.get(queries[i]);
        return ans;
    }
    int getLength(TreeNode root) {
        if (root == null) return -1;    
        int l = getLength(root.left);            
        int r = getLength(root.right);        
        int len = Math.max(l, r) + 1;  
        height.put(root.val, len);         
        return len;         
    }
}      

• 使用dfs序來給每一個節點進行标号,dfs即dfs第一次搜尋到該節點的次序，通過該種方式，可以發現以根節點出發，通路所有子節點的次序必然是連續的，那麼可以統計該節點為根的子樹能夠包括的範圍。使用depth[] 來統計每個以dfs序為索引的節點的深度，如5:d[1] = 0。
• 當删除某個節點，如2，等于删除以2為根的子樹所包含的所有範圍即, 那麼我們隻需要在和統計每個節點的最大深度。可以使用字首最大值和字尾最大值快速求出和的最大深度進行比較。

• 時間複雜度：
• 空間複雜度：

class Solution {
    int N = 100005;
    int[] l = new int[N], r = new int[N], depth = new int[N], lmax = new int[N], rmax= new int[N];
    int cnt = 0;
    public int[] treeQueries(TreeNode root, int[] queries) {
        dfs(root, 0);
        int[] ans = new int[queries.length];
        for (int i = 1; i <= cnt; i++) lmax[i] = Math.max(depth[i], lmax[i - 1]);
        for (int i = cnt; i >= 0; i--) rmax[i] = Math.max(depth[i], rmax[i + 1]);
        for (int i = 0; i < queries.length; i++) ans[i] = Math.max(lmax[l[queries[i]] - 1],  rmax[r[queries[i]] + 1]);
        return ans;
    }
    void dfs(TreeNode root, int level) {
        if (root == null) return;
        depth[++cnt] = level;
        l[root.val] = cnt;
        dfs(root.left, level + 1);
        dfs(root.right, level + 1);
        r[root.val] = cnt;
    }
}