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

• `````` 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;
}
``````

};

• 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 nume=0;
int ind[100000];
int numv=0;
void init()
{
memset(ind,0,sizeof(ind));
}
{
e[nume][0]=y;
}
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]++;
}
if(fa->val==r->val+1)
{
ind[curid]++;
}
}
dfs(r->left,r,curid);
dfs(r->right,r,curid);
}

int ans=1;
void dfs_getans(int v,int lev)
{
ans=max(ans,lev);
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;
}``````

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