Advertisement
imashutosh51

Longest zig-zag path in a binary tree

Aug 11th, 2022 (edited)
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. /*
  2. Logic:
  3. ->traversed the tree.
  4. ->leaf node alone can't contribute in zig zag maximum path so it will return 0.
  5. ->zig-zag path can started from any node and in any direction,so answer
  6.   get's updted at every node.
  7. ->Assume that parent of current node is the starting node of zig zag maximum path,
  8.   then reversed direction of child of current node can only contribute in
  9.   zig zag path.so we only returned that path zig zag's.
  10. */
  11. int ans=0;
  12. int fun(TreeNode* root,char dir){
  13.     if(!root->left && !root->right) return 0;
  14.     int n1=0,n2=0;
  15.     if(root->left) n1=fun(root->left,'l');
  16.     if(root->right) n2=fun(root->right,'r');
  17.     ans=max(ans,max(n1,n2)+1);
  18.     if(root->left && dir=='r') return n1+1;
  19.     if(root->right && dir=='l') return n2+1;
  20.     return 0;
  21. }
  22. class Solution {
  23. public:
  24.     int longestZigZag(TreeNode* root) {
  25.         ans=0;
  26.         if(!root) return 0;
  27.         fun(root,'c');
  28.         return ans;
  29.     }
  30. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement