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 最长相同值路径
，如需转载请自行联系原博主。