Description
给定\(n\)个结点的二叉树，每个结点具有权值\(v_i\)，求出树上的最长相同权值路径（可以不经过根结点）。
Constraints
- \(0 \le n \le 10^4\)
- \(-1000 \le v_i \le 1000\)
Solution
和124一个套路。
这里\(dp[u]\)求的是以\(u\)子树（且为路径起点的）路径长度，因此单个结点的情况下是\(0\)。
Code
class Solution {
public:
int longestUnivaluePath(TreeNode* root) {
unordered_map<TreeNode*, int> dp;
auto DP = [&](auto &&DP, TreeNode * cur) {
if(!cur) return 0;
auto lc = cur->left;
auto rc = cur->right;
auto lres = DP(DP, lc);
auto rres = DP(DP, rc);
int ans = 0;
if(lc && lc->val == cur->val) {
ans = lres + 1;
}
if(rc && rc->val == cur->val) {
ans = max(ans, rres + 1);
}
return dp[cur] = ans;
};
int ans = DP(DP, root);
for(auto [cur, _] : dp) {
auto lc = cur->left;
auto rc = cur->right;
if(lc && lc->val == cur->val) {
ans = max(ans, dp[lc] + 1);
}
if(rc && rc->val == cur->val) {
ans = max(ans, dp[rc] + 1);
}
if(lc && rc && lc->val == rc->val && lc->val == cur->val) {
ans = max(ans, dp[lc] + dp[rc] + 2);
}
}
return ans;
}
};