做网站涉及到哪些/seo关键词推广案例

带权的二叉树里找一棵节点数最多的子树使得权值和结构都对称

1e6

这题最主要的点还是计算时间复杂度 刚看到的时候总是觉得每个点都要再往下找 那么这个复杂度显然是n方的 但是实际上是

n+n/2+n/2+n/4+n/4+...+1 复杂度是严格的nlogn

另外就是对树的递归的处理 我总是想在一个递归里做完所有的事情

bool dfs(int x,int y)
{if(x==-1&&y==-1)return true;if(x==-1){dfs(l[y],r[y]);return false;}if(y==-1){dfs(l[x],r[x]);return false;}if(w[x]!=w[y]||num[x]!=num[y]){dfs(l[x],r[x]);dfs(l[y],r[y]);return false;}if(dfs(l[x],r[y])&&dfs(l[y],r[x])){ans=max(ans,num[x]*2+1);return true;}dfs(l[x],r[x]);dfs(l[y],r[y]);return false;
}

但是注意到 当检测完不对称之后 又继续去检测子树 那么在一次调用里在最坏情况下会引起4次子调用 于是时间复杂度一定比之前的式子大

正解应该是对每个点都进行检测 控制子调用的次数 确保严格的nlogn

bool dfs(int x,int y)
{if(x==-1&&y==-1)return true;if(x==-1||y==-1||w[x]!=w[y]||num[x]!=num[y])return false;return dfs(l[x],r[y])&&dfs(l[y],r[x]);
}