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;
    }
};

LeetCode-687 Longest Univalue Path