# 687. Longest Univalue Path

• 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 class Solution { public: int longestUnivaluePath(TreeNode* root) { int ans = 0; longestUnivaluePathDownFrom(root, ans); return ans; } private: int longestUnivaluePathDownFrom(TreeNode* root, int& ans) { if (root == nullptr) return 0; const int l = longestUnivaluePathDownFrom(root->left, ans); const int r = longestUnivaluePathDownFrom(root->right, ans); const int arrowLeft = root->left && root->left->val == root->val ? l + 1 : 0; const int arrowRight = root->right && root->right->val == root->val ? r + 1 : 0; ans = max(ans, arrowLeft + arrowRight); return max(arrowLeft, arrowRight); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public int longestUnivaluePath(TreeNode root) { longestUnivaluePathDownFrom(root); return ans; } private int ans = 0; private int longestUnivaluePathDownFrom(TreeNode root) { if (root == null) return 0; final int l = longestUnivaluePathDownFrom(root.left); final int r = longestUnivaluePathDownFrom(root.right); final int arrowLeft = root.left != null && root.left.val == root.val ? l + 1 : 0; final int arrowRight = root.right != null && root.right.val == root.val ? r + 1 : 0; ans = Math.max(ans, arrowLeft + arrowRight); return Math.max(arrowLeft, arrowRight); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def longestUnivaluePath(self, root: Optional[TreeNode]) -> int: ans = 0 def longestUnivaluePathDownFrom(root: Optional[TreeNode]) -> int: nonlocal ans if not root: return 0 l = longestUnivaluePathDownFrom(root.left) r = longestUnivaluePathDownFrom(root.right) arrowLeft = l + 1 if root.left and root.left.val == root.val else 0 arrowRight = r + 1 if root.right and root.right.val == root.val else 0 ans = max(ans, arrowLeft + arrowRight) return max(arrowLeft, arrowRight) longestUnivaluePathDownFrom(root) return ans