LeetCode 687. 最长同值路径（二叉树，递归）

示例 1:
输入:

              5
             / \
            4   5
           / \   \
          1   1   5
输出:
2

示例 2:
输入:

              1
             / \
            4   5
           / \   \
          4   4   5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。

class Solution {
	int maxlen = 0;
public:
    int longestUnivaluePath(TreeNode* root) {
    	if(!root)
    		return 0;
        sameValue(root);//跟root值一样的
        longestUnivaluePath(root->left);
        longestUnivaluePath(root->right);
        return maxlen;
    }

    int sameValue(TreeNode* root)
    {
    	if(root == NULL)
    		return 0;
    	int leftLen = 0, rightLen = 0;
    	if(root->left && root->left->val == root->val)
    		leftLen = sameValue(root->left);
    	if(root->right && root->right->val == root->val)
    		rightLen = sameValue(root->right);
        maxlen = max(leftLen+rightLen, maxlen);
        //最大值实时更新，根左右连通，最长路径
    	return 1+max(leftLen, rightLen);
    	//传出去，只能选择一边的路径
    }
};

class Solution {
	int maxlen = 0;
public:
    int longestUnivaluePath(TreeNode* root) {
        sameValue(root);
        return maxlen;
    }

    int sameValue(TreeNode* root)
    {
    	if(root == NULL)
    		return 0;
    	int leftLen = sameValue(root->left);
    	int rightLen = sameValue(root->right);
    	int L = 0, R = 0;
    	if(root->left && root->left->val == root->val)
    		L = leftLen+1;
    	if(root->right && root->right->val == root->val)
    		R = rightLen+1;
        maxlen = max(L+R, maxlen);
    	return max(L, R);
    }
};