# 1372. Longest ZigZag Path in a Binary Tree

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 struct T { int leftMax; int rightMax; int subtreeMax; }; class Solution { public: int longestZigZag(TreeNode* root) { return dfs(root).subtreeMax; } private: T dfs(TreeNode* root) { if (root == nullptr) return {-1, -1, -1}; const T left = dfs(root->left); const T right = dfs(root->right); const int leftZigZag = left.rightMax + 1; const int rightZigZag = right.leftMax + 1; const int subtreeMax = max({leftZigZag, rightZigZag, left.subtreeMax, right.subtreeMax}); return {leftZigZag, rightZigZag, subtreeMax}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class T { public int leftMax; public int rightMax; public int subtreeMax; public T(int leftMax, int rightMax, int subtreeMax) { this.leftMax = leftMax; this.rightMax = rightMax; this.subtreeMax = subtreeMax; } } class Solution { public int longestZigZag(TreeNode root) { return dfs(root).subtreeMax; } private T dfs(TreeNode root) { if (root == null) return new T(-1, -1, -1); T left = dfs(root.left); T right = dfs(root.right); final int leftZigZag = left.rightMax + 1; final int rightZigZag = right.leftMax + 1; final int subtreeMax = Math.max(Math.max(leftZigZag, rightZigZag), Math.max(left.subtreeMax, right.subtreeMax)); return new T(leftZigZag, rightZigZag, subtreeMax); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class T: def __init__(self, leftMax: int, rightMax: int, subtreeMax: int): self.leftMax = leftMax self.rightMax = rightMax self.subtreeMax = subtreeMax class Solution: def longestZigZag(self, root: Optional[TreeNode]) -> int: def dfs(root: Optional[TreeNode]) -> T: if not root: return T(-1, -1, -1) left = dfs(root.left) right = dfs(root.right) leftZigZag = left.rightMax + 1 rightZigZag = right.leftMax + 1 subtreeMax = max(leftZigZag, rightZigZag, left.subtreeMax, right.subtreeMax) return T(leftZigZag, rightZigZag, subtreeMax) return dfs(root).subtreeMax