Title
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.
题目大意：判断具有同样数字的最长路径，我做的还是不合理，多了重复计算，不过也还好，ac，看solution可以更简化些
Solution
//cpp:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int ans=0;
int dfs(TreeNode* t,int k){
if(!t)
return 0;
if(t->val!=k)
return 0;
return 1+max(dfs(t->left,k),dfs(t->right,k));
}
int longestUnivaluePath(TreeNode* root) {
if(!root)
return 0;
int left=dfs(root->left,root->val);
int right=dfs(root->right,root->val);
return max(left+right,max(longestUnivaluePath(root->left),longestUnivaluePath(root->right)));
}
};
solution有对应的不重复的计算方法，有时间去看下！！