Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Logic:
- ->traversed the tree.
- ->leaf node alone can't contribute in zig zag maximum path so it will return 0.
- ->zig-zag path can started from any node and in any direction,so answer
- get's updted at every node.
- ->Assume that parent of current node is the starting node of zig zag maximum path,
- then reversed direction of child of current node can only contribute in
- zig zag path.so we only returned that path zig zag's.
- */
- int ans=0;
- int fun(TreeNode* root,char dir){
- if(!root->left && !root->right) return 0;
- int n1=0,n2=0;
- if(root->left) n1=fun(root->left,'l');
- if(root->right) n2=fun(root->right,'r');
- ans=max(ans,max(n1,n2)+1);
- if(root->left && dir=='r') return n1+1;
- if(root->right && dir=='l') return n2+1;
- return 0;
- }
- class Solution {
- public:
- int longestZigZag(TreeNode* root) {
- ans=0;
- if(!root) return 0;
- fun(root,'c');
- return ans;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement