Leetcode 6233 -- DFS序列 | 两遍DFS

题目描述

给定我们一棵树，和一组查询，每个查询给出一个节点，让我们求删除以这个节点为根（包括这个节点）的子树中的所有节点之后（并不是真的删除），剩下的树中节点的最大高度。（树的高度是从根到树中某个节点的 最长简单路径中的边数 。）

思路

$DFS$ 序列

对于树的题目，学习到了一种新的算法（思路） – $DFS$ 序列
即将树通过 $DFS$ 序转成序列。
子树里的所有点是 $DFS$ 序里的一个连续区间。因此本题可以被转化为如下问题：
给定一个序列，每次删除一个连续区间，求序列里剩下的数的最大值。
显然删除一个连续区间后，序列会剩下一个前缀以及一个后缀。
我们预处理前缀 $max$ 和后缀 $max$，就能 $O(1)$ 回答每个询问。复杂度 $O(n+q)$。（$n$为数中节点数，$q$ 为查询个数）。

两遍 $DFS$

第一遍 $DFS$ 求每个节点的高度。第二次 $DFS$ 求“删除”该节点后的最大高度。
解释一下第二次 $DFS，如果我们删除了某一个节点和它的子树，那么此时树的最大高度就是在继续 $DFS$ 它之前的最大高度。
但是我们在 $DFS$ 的过程中是无法知道这个值的，所以我们要在 $DFS$ 的参数中维护这个值（$res{t}_h$）来表示遍历到当前节点之前，树的最大高度。
那么在进入下一次 $DFS$ 时，我们就要更新这个值。具体看代码吧。

代码 – dfs序列（双百）

class Solution {
public:
    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
        int height[100010], son[100010];
        int l[100010], r[100010];
        int pos[100010];
        memset(height, 0, sizeof height);
        memset(son, 0, sizeof son);
        vector<int> res, path;
        
        function<int(TreeNode *, int)> dfs = [&](TreeNode *root, int depth) -> int {
            if(root == NULL)    return 0;
            int t = root->val;
            path.push_back(t);
            height[t] = depth;  
            son[t] = 1;
            son[t] += dfs(root->left,  depth + 1);
            son[t] += dfs(root->right, depth + 1);
            return son[t];
        };
        dfs(root, 0);
        int n = path.size();
        l[path[0]] = height[path[0]], r[path[n - 1]] = height[path[n - 1]], pos[path[0]] = 0;
        for(int i = 1, j = n - 2; i < n; i ++ , j -- )
        {
            pos[path[i]] = i;
            l[path[i]] = max(height[path[i]], l[path[i - 1]]);
            r[path[j]] = max(height[path[j]], r[path[j + 1]]);
        }

        // cout << "path: "; for(auto &x : path) cout << x << ' ';   cout << endl;
        // for(auto &x : path) cout << l[x] << ' ';    cout << endl;
        // for(auto &x : path) cout << r[x] << ' ';    cout << endl;
        
        for(auto &x : queries)
        {
            int p = pos[x];
            // cout << "p: " << p << ' ' << p + son[x] << endl;
            // 边界检查
            int lmaxn = (p == 0) ? 0 : l[path[p - 1]];
            int rmaxn = (p + son[x] >= n) ? 0 : r[path[p + son[x]]];
            int maxn = max(lmaxn, rmaxn);
            res.push_back(maxn);
        }

        return res;
    }
};
/* 1. 预处理每个节点到根节点的距离（高度）
   2. 预处理每个节点的孩子节点的个数
*/

代码 – 两遍 bfs（双百）

class Solution {
public:
    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
        unordered_map<TreeNode *, int> height;
        function<int(TreeNode *)> get_height = [&](TreeNode *node) -> int {
            return node ? height[node] = 1 + max(get_height(node->left), get_height(node->right)) : 0; 
        }; // 一行 dfs
        get_height(root);

        int res[height.size() + 1]; // 可以对 map 求 size
        function<void(TreeNode *, int, int)> dfs = [&](TreeNode *node, int depth, int rest_h) -> void {
            if(node == nullptr) return ;
            res[node->val] = rest_h; // 删除该节点之后的树的最大高度等于 dfs 该节点之前树的最大高度
            // 往下 dfs 并 维护 rest_h
            dfs(node->left, depth + 1, max(rest_h, depth + 1 + height[node->right]));
            dfs(node->right, depth + 1, max(rest_h, depth + 1 + height[node->left]));
        };
        dfs(root, -1, 0);
        for(auto &x : queries)  x = res[x];  // 实在是妙！节省空间
        return queries;
    }
};