Leetcode 求最长单值路径的问题

Question

问题：

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

The length of path between two nodes is represented by the number of edges between them.

source

对此的解决方案是：

class Solution 
{
public:
    int max_len = INT_MIN;
    
    int longestUnivaluePath(TreeNode* root) 
    {
        if(!root)
            return 0;
    
        helper(root, root->val);
        
        return max_len;
    }
    
    int helper(TreeNode* root, int prev_value)
    {
        if(!root)
            return 0;
        
        int left = helper(root->left, root->val);
        int right = helper(root->right, root->val);
        
        max_len = std::max(left + right, max_len); // Why do we do this? I have no idea
        
        if(root->val == prev_value)
            return std::max(left, right) + 1;
        return 0;
    }
};

我们为什么这样做：max_len = std::max(left + right, max_len);这部分对我来说没有意义。如果有人真的能简单地解释一下，我将不胜感激。

Answer 1

最长的路径不必严格降序，对吧？例如下面树中最长单值路径的长度为2：

    3
   / \
  3   3

在他们的算法中，
left 是 node.
左分支下最长降序单值路径的长度 right 是 node.
右分支下最长降序单值路径的长度合并后，left + right 是通过节点 node 的最长单值路径的长度，这是新的候选路径。

所以有问题的那一行实际上意味着
max_len = std::max(candidate_len, max_len);
这是一个规范的运行 max 算法：它按顺序逐一处理候选值，并保留迄今为止在 max_len 中看到的最大值。最终，max_len 将以所有候选人的最大值结束。

Leetcode 求最长单值路径的问题

Leetcode question to finding the longest univalue path

c++

binary-tree