LeetCode Solutions
687. Longest Univalue Path
Time: $O(n)$ Space: $O(h)$
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);
}
};
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);
}
}
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