2458.移除子树后的二叉树高度

链接：2458.移除子树后的二叉树高度
难度：Hard
标签：树、深度优先搜索、广度优先搜索、数组、二叉树
简介：返回一个长度为 m 的数组 answer ，其中 answer[i] 是执行第 i 个查询后树的高度。

题解 1 - cpp

• 编辑时间：2022-10-30
• 执行用时：368ms
• 内存消耗：222.5MB
• 编程语言：cpp
• 解法介绍：两次 dfs，第一次统计出每颗子树的高度，第二次记录层高，统计当前子树被移除后的剩余高度，通过最大高度和 level+右子树高度的最大值获取。

class Solution {
public:
    typedef pair<int, int> node;
    unordered_map<int, node> m;
    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
        m[-1] = make_pair(0, 0);
        dfs1(root);
        dfs2(root);
        vector<int> ans;
        for (auto &q : queries) ans.push_back(m[q].second);
        return ans;
    }
    int dfs1(TreeNode *node) {
        if (node == nullptr) return 0;
        int l = dfs1(node->left), r = dfs1(node->right), h = max(l, r) + 1;
        m[node->val] = make_pair(h, 0);
        return h;
    }
    void dfs2(TreeNode *node, int level = 0, int curH = 0) {
        if (node == nullptr) return;
        m[node->val].second = curH;
        int l = node->left == nullptr ? -1 : node->left->val,
            r = node->right == nullptr ? -1 : node->right->val;
        dfs2(node->left, level + 1, max(curH, level + m[r].first));
        dfs2(node->right, level + 1, max(curH, level + m[l].first));
    }
};