Leetcode 687 Solution

This article provides solution to leetcode question 687 (longest-univalue-path)

https://leetcode.com/problems/longest-univalue-path

Solution

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { int ans; public: int _longestUnivalueDepth(TreeNode* root) { if (!root) return 0;
int left_depth = root->left ? _longestUnivalueDepth(root->left) : 0; int right_depth = root->right ? _longestUnivalueDepth(root->right) : 0;
int path = 0; int depth = 0; if (root->left && root->val == root->left->val) { path += left_depth + 1; depth = max(depth, left_depth + 1); } if (root->right && root->val == root->right->val) { path += right_depth + 1; depth = max(depth, right_depth + 1); }
ans = max(ans, path); return depth; }
int longestUnivaluePath(TreeNode* root) { ans = 0; _longestUnivalueDepth(root); return ans; } };