Description

给定n个结点的二叉树，每个结点具有权值vi，求出树上的最长相同权值路径（可以不经过根结点）。

Constraints

  • 0≤n≤104
  • −1000≤vi≤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;
    }
};

LeetCode-687 Longest Univalue Path