687. 最长同值路径

687. 最长同值路径

每次dfs返回的是以该节点为结尾的最长串长度

/**
 * 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 res;
    int longestUnivaluePath(TreeNode* root) {
        res=0;
        dfs(root);
        return res;
    }
    
    int dfs(TreeNode *root){
        if(!root)return 0;
        
        int leftmax=0,rightmax=0,cur=0;
        leftmax=dfs(root->left);
        rightmax=dfs(root->right);
        
        if(root->left && root->left->val==root->val) {
            leftmax++;
            cur=max(cur,leftmax);
        }
        if(root->right && root->right->val==root->val){
            rightmax++;
            cur=max(cur,rightmax);
        }
        if(root->left && root->right 
           && root->right->val==root->val 
           && root->left->val==root->val) res=max(res,leftmax+rightmax);
        
        res=max(res,cur);
       
        return cur;
    }
};