leetcode1372dp求交错路径长

• bfd+dp

unordered_map<TreeNode* ,int>d,p;
queue<pair<TreeNode* ,TreeNode*>>q;
int dp(TreeNode* root){
    d[root]=p[root]=0;
    q.push({root,nullptr});
    while(!q.empty()){
        auto x=q.front();q.pop();
        auto y=x.second();
        auto u=x.first();
        d[u]=p[u]=0;//因为在经过所有节点时，可能有些d或p值不会被赋值，导致后面遍历找最大值时漏掉
        if(y){
            if(y->left)d[u]=p[y]+1;
            if(y->right)p[u]=d[y]+1;
        }
        if(u->left)q.push(u->left,u);
        if(u->right)q,push(u->right,u);
    }
}
int longestZigZag(TreeNode* root){
    dp(root);
    int maxans=0;
    for(const auto &u:f)maxans=max(maxans,max(u.first,p[u.first]));
    return maxans;
}