[687]最长同值路径

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:

5
             / \
            4   5
           / \   \
          1   1   5

输出:

2

示例 2:
输入:

1
             / \
            4   5
           / \   \
          4   4   5

输出:

2

注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res = 0;
    int longestUnivaluePath(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* root){
        if(root == nullptr) return 0;
        if(root->left == nullptr && root->right == nullptr){
            return 0;
        }
        int left = dfs(root->left);
        int right = dfs(root->right);
        int arrow_left = 0, arrow_right = 0;
        if(root->left != nullptr && root->val == root->left->val){
            arrow_left += 1 + left;
        }

        if(root->right != nullptr && root->val == root->right->val){
            arrow_right += 1 + right;
        }
        res = max(res, arrow_left + arrow_right);
        return max(arrow_left,arrow_right);
    }
};