2 c++ solution ! o(N) . get longest topo path


  • 0
     class Solution {
    
    public:
    int ans=1;
    pair<int,int> dfs(TreeNode* r)
    {
        pair<int ,int>retl(1,1),retr(1,1);
        int inc=1,dec=1;   
        if(r->left!=nullptr)
            {
                retl=dfs(r->left);
                if(r->left->val==r->val+1)
                     dec=max(retl.second+1,dec);
                 if(r->left->val==r->val-1)
                     inc=max(retl.first+1,inc);
            }
                
        if(r->right!=nullptr)
            {
                retr=dfs(r->right);
                 if(r->right->val==r->val+1)
                     dec=max(retr.second+1,dec);
                 if(r->right->val==r->val-1)
                     inc=max(retr.first+1,inc);
            }
        
        ans=max(ans,inc+dec-1);
        return pair<int,int>(inc,dec);
    }
    
    int longestConsecutive(TreeNode* root) 
    {
        if(root==nullptr)
            return 0;
        dfs(root);
        return ans;
    }
    

    };


  • 0

    there is another just 2 times dfs solution.(1 travel to build topo, then get longest topo path! if a=b-1, then there is an edge b->a)

    int e[100000][2];
    int head[100000];
    int nume=0;
    int ind[100000];
    int numv=0;
    void init()
    {
        memset(head,-1,sizeof(head));
        memset(ind,0,sizeof(ind));
    }
    void adde(int x,int y)
    {
        e[nume][0]=y;
        e[nume][1]=head[x];
        head[x]=nume++;
    }
    void dfs(TreeNode *r,TreeNode *fa,int faId)
    {
        if(r==nullptr)
            return ;
        int curid=numv++;
        if(fa!=nullptr)
        {
            if(fa->val==r->val-1)
            { 
                ind[faId]++;
                adde(curid,faId,0);
            }
            if(fa->val==r->val+1)
            { 
                 ind[curid]++;
                adde(faId,curid,0);
            }
        }
           dfs(r->left,r,curid);
           dfs(r->right,r,curid);
    }
    
    int ans=1;
    void dfs_getans(int v,int lev)
    {
        ans=max(ans,lev);
        for(int j=head[v];j!=-1;j=e[j][1])
            dfs_getans(e[j][0],lev+1);
    }
    int longestConsecutive(TreeNode* root) 
    {
         if(root==nullptr)
            return 0;
         init();
         dfs(root,nullptr,-1);
         for(int i=0;i<numv;i++)
         {
             if(ind[i]==0)
                 dfs_getans(i,1);
         }
        return ans;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.