题目分析

本题是第317场周赛的最后一题，题目的难度比较大。数据范围是1e5，因此不能使用$ O(n^2) $的算法来解决。只能想一下是否有$O(n)$或者$O(log(n))$的方法。

深度优先搜索

因为本题要删除某个节点，然后寻找树的最大高度。因此会想到先遍历整棵树，先搜索每一个节点作为根对应的高度。

然后思考一个最重要的点，一个节点N，去掉左孩子L，剩下子树的最大高度 = max(根到左孩子的高度 + 右孩子R的高度, 不经过节点N的高度)

一个节点N，去掉右孩子R，剩下子树的最大高度 = max(根到右孩子的高度 + 左孩子L的高度, 不经过节点N的高度)

这样就可以再次遍历这棵树，在遍历的过程中记录删除每个点的最大高度，然后直接查询即可。

算法的**时间复杂度为O(n)，空间复杂度为O(n)**。

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 Solution {
    HashMap<TreeNode, Integer> heightMap = new HashMap<>();
    
    private int[] nodeRes;

    public int[] treeQueries(TreeNode root, int[] queries) {
        heightMap.put(null, 0);
        getHeight(root);
        nodeRes = new int[heightMap.size()];
        dfs(root, -1, 0);
        int n = queries.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = nodeRes[queries[i]];
        }
        return res;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = getHeight(node.left);
        int right = getHeight(node.right);
        int height = Math.max(left, right) + 1;
        heightMap.put(node, height);
        return height;
    }
    
    private void dfs(TreeNode node, int height, int otherHeight) {
        if (node == null) {
            return;
        }
        height++;
        nodeRes[node.val] = otherHeight;
        dfs(node.left, height, Math.max(otherHeight, height + heightMap.get(node.right)));
        dfs(node.right, height, Math.max(otherHeight, height + heightMap.get(node.left)));
    }
}

刷题总结

树和图的题目，一直是Leetcode竞赛的难题，小伙伴们也不用过多害怕。在笔试面试中一般不会出很难的树和图，但是从树和图中也可以学到很多重要的算法。如DFS、BFS、并查集、拓扑排序、递归等都是图论的思想，也是非常重要的。