Leetcode问题以寻找最长的单值路径 [英] Leetcode question to finding the longest univalue path

问题描述

问题:

给出一棵二叉树，找到路径中每个节点具有相同值的最长路径的长度.此路径可能会通过根，也可能不会通过根.

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.

源

对此的解决方案是:

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);这部分对我来说没有意义.如果有人能简单地解释它，我将不胜感激.

Why do we do this: max_len = std::max(left + right, max_len); This part does not make sense to me. If anyone can actually explain it simply I would greatly appreciate the insight.

推荐答案

最长的路径不必严格地下降，对吗?例如，以下树中最长的单值路径的长度为2:

The longest path doesn't have to be strictly descending, right? For example, the length of the longest univalue path in the following tree is 2:

    3
   / \
  3   3

在他们的算法中，
left是沿着node左分支的最长下降单值路径的长度.
right是沿着node右分支的最长下降单值路径的长度.
组合在一起的left + right是经过 节点node的最长单值路径的长度，这是新的候选路径.

In their algorithm,
left is the length of the longest descending univalue path down the left branch of node.
right is the length of the longest descending univalue path down the right branch of node.
Combined, left + right is the length of the longest univalue path going through the node node, which is the new candidate path.

因此，该行实际上表示
max_len = std::max(candidate_len, max_len);
这是一种规范的运行最大值算法:它依次逐个处理候选值，并保持到目前为止在max_len中看到的最大值.最终，max_len将以所有候选者的最大值结束.

So the line in question actually means
max_len = std::max(candidate_len, max_len);
which is a canonical running max algorithm: it processes the candidate values sequentially, one by one, and keeps the maximum value seen thus far in max_len. Eventually, max_len will end up with the maximum value of all candidates.

这篇关于Leetcode问题以寻找最长的单值路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！