一、定义
删除一个点后整个树的最大深度会改变,这些点形成的链即所谓的重链。可以发现删除重链之外的点树的最大深度都不会改变
二、建重链
可以发现重链是从根节点开始,如果两个子结点的深度不一样,深度更大的那个点即重链上的点(这里的深度是指每个点到叶结点的最大距离)
我们用一个son数组来记录从根节点开始重链上的每个点是它的左儿子(0)还是右儿子(1),当走到某个结点,它的左右子结点深度一样的时候,删除它的所有子结点就都不会影响到树的最大深度,重链就结束了
三、删重链
删除重链上的某个点后剩余树的最大值应该是讨论删除从根节点到当前结点的最大值,比如删除C点或B点后的最大值,为删除A点后T所在的分支的深度
四、Example:
const int N = 1e5+10;
int tr[N][2], son[N], ans[N], d[N], n;
int dfs(TreeNode* u)
{
if (!u) return 0;
n ++;
int l = dfs(u->left), r = dfs(u->right), v = u->val;
if (l) tr[v][0] = u->left->val;
if (r) tr[v][1] = u->right->val;
if (l > r) son[v] = 0; // 建重链的时候一定要两侧子树深度不一样
else if (r > l) son[v] = 1;
return d[v] = max(l, r) + 1;
}
class Solution {
public:
vector<int> treeQueries(TreeNode* root, vector<int>& queries) {
n = 0;
memset(tr, 0, sizeof tr);
memset(son, -1, sizeof son);
dfs(root); // 将所有点到叶结点的深度求出来,同时将重链求出来
for (int i = 1; i <= n; i ++) ans[i] = d[root->val]; // 将删除所有点后剩余的最大深度初始化为根结点的深度
int cur = root->val, path = 0, maxd = 0;
while (~son[cur]) // 只有删除重链上的点会影响剩余树的最大高度,验证将重链上的点删除,将答案处理出来
{
path ++;
int k = son[cur];
maxd = max(maxd, path + d[tr[cur][k ^ 1]]);
ans[tr[cur][k]] = maxd; // 记录删除当前结点的k这个儿子的后剩余的最大值
cur = tr[cur][k];
}
vector<int> res;
for (auto &t : queries) res.push_back(ans[t] - 1); // 叶结点的高度我们算的1,实际要减去1
return res;
}
};