Leetcode 6233 -- dfs序

题目描述

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

思路

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

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. 预处理每个节点的孩子节点的个数
*/