leetcode 687. 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.

思路：
对于每一棵子树，我们可以可以选择左边最大，右边最大，或者左边+右边
而这些选择是在某种条件下才可能发生。比如

Input:
            4   
           /    
          4   4   

当左边和右边相等并且等于root时，我们才可能合并左右。 而在左边不能与root或则右边不等于root,我们只需要取最大的一个作为这棵子树的最大值了，代码如下

/**
 * 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;
    int dfsmax(TreeNode* root) {
        if (root == nullptr) return 0;
        int l = dfsmax(root->left);
        int r = dfsmax(root->right);
        int m1 = 0;
        int m2 = 0;
        if (root->left == nullptr || root->left->val != root->val) l = 0;
        else if (root->left->val == root->val) ++l, m1 = 1;
        
        if (root->right == nullptr || root->right->val != root->val) r = 0;
        else if (root->right->val == root->val) ++r, m2 = 1;
        
        if (m1 && m2) ans = max(ans, l + r);
        ans = max(ans, max(l, r));
        return max(l, r);
    }
    int longestUnivaluePath(TreeNode* root) {
        ans = 0;
        dfsmax(root);
        return ans;
    }
};