spider68

min difference b/w nodes

Mar 16th, 2020
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.58 KB | None | 0 0
  1. bool find(Node*root,int a,vector<int>&v)
  2. {
  3. if(!root)return 0;
  4. v.push_back(root->data);
  5. if(root->data==a)return 1;
  6. if((root->left&&find(root->left,a,v))||(root->right&&find(root->right,a,v)))return true;
  7. v.pop_back();
  8. return 0;
  9. }
  10. int findDist(Node* root, int a, int b) {
  11. if(b==a)return 0;
  12. vector<int>v1,v2;
  13. find(root,a,v1);
  14. find(root,b,v2);
  15. int i;
  16. for(i=0;i<v1.size()&&i<v2.size();i++)
  17. {
  18. if(v1[i]!=v2[i])break;
  19. }
  20. // cout<<v1.size()<<v2.size()<<i<<endl;
  21. int s=v1.size()+v2.size()-2*i;
  22. return s;
  23. }
Add Comment
Please, Sign In to add comment