[LeetCode] 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.

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

Example 1:

Input:

              5
             / \
            4   5
           / \   \
          1   1   5

Output:

2 

Example 2:

Input:

              1
             / \
            4   5
           / \   \
          4   4   5

 Output:

2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

这道题让我们求最长的相同值路径，跟之前那道Count Univalue Subtrees十分的类似，解法也很类似。对于这种树的路径问题，递归是不二之选。在递归函数中，我们首先对其左右子结点调用递归函数，得到其左右子树的最大相同值路径，下面就要来看当前结点和其左右子结点之间的关系了，如果其左子结点存在且和当前节点值相同，则left自增1，否则left重置0；同理，如果其右子结点存在且和当前节点值相同，则right自增1，否则right重置0。然后用left+right来更新结果res。而调用当前节点值的函数只能返回left和right中的较大值，因为如果还要跟父节点组path，就只能在左右子节点中选一条path，当然选值大的那个了，参见代码如下：

解法一：

public:
    int longestUnivaluePath(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        helper(root, root, res);
        return res;
    }
    int helper(TreeNode* node, TreeNode* parent, int& res) {
        if (!node) return 0;
        int left = helper(node->left, node, res);
        int right = helper(node->right, node, res);
        left = (node->left && node->val == node->left->val) ? left + 1 : 0;
        right = (node->right && node->val == node->right->val) ? right + 1 : 0;
        res = max(res, left + right);
        return max(left, right);
    }
};

下面这种解法使用了两个递归函数，使得写法更加简洁了，首先还是先判断root是否为空，是的话返回0。然后对左右子节点分别调用当前函数，取其中较大值保存到变量sub中，表示左右子树中最长的相同值路径，然后就是要跟当前树的最长相同值路径比较，计算方法是对左右子结点调用一个helper函数，并把当前结点值传进去，把返回值加起来和sub比较，去较大值返回。在helper函数里，当当前结点为空，或者当前节点值不等于父结点值的话，返回0。否则结返回对左右子结点分别调用helper递归函数中的较大值加1，我们发现这种写法跟求树的最大深度很像，参见代码如下：

解法二：

public:
    int longestUnivaluePath(TreeNode* root) {
        if (!root) return 0;
        int sub = max(longestUnivaluePath(root->left), longestUnivaluePath(root->right));
        return max(sub, helper(root->left, root->val) + helper(root->right, root->val));
    }
    int helper(TreeNode* node, int parent) {
        if (!node || node->val != parent) return 0;
        return 1 + max(helper(node->left, node->val), helper(node->right, node->val));
    }
};

本文转自博客园Grandyang的博客，原文链接：[LeetCode] Longest Univalue Path 最长相同值路径

，如需转载请自行联系原博主。