687. Longest Univalue Path

int longestUnivaluePath(TreeNode* root) {
    if (!root) return 0;
    int m=0;
    int lr = DFS(root, root->val, 0, m);
	// 递归选择起点，m为子子节点间的边数，lr为父子节点间的边数
    return max(max(lr, m), longestUnivaluePath(root->left), longestUnivaluePath(root->right));
}

int DFS(TreeNode* root, int val, int depth, int &m) {
	// 触底或值不再相等的时候返回边数
    if (!root || root->val!=val) return depth-1;
	// 深搜左子树和右子树
    int l = DFS(root->left, val, depth+1, m);
    int r = DFS(root->right, val, depth+1, m);
	// 总是保存最大的子子路径边数
    m = max(m, l+r-2*depth);
	// 父子路径返回大的
    return max(l, r);
}

int longestUnivaluePath(TreeNode* root) {
    if (!root) return 0;
    int m=0;
    DFS(root, m);
    return m;
}

int DFS(TreeNode* root, int &m) {
	// 递归搜索左子树的边数和右子树的边数
    int l=root->left ? DFS(root->left, m) : 0;
    int r=root->right ? DFS(root->right, m) : 0;
	// 值相等，这条边就可以纳入计数
    l = (root->left && root->left->val == root->val) ? l+1 : 0;
    r = (root->right && root->right->val == root->val) ? r+1 : 0;
	// 当前节点出发，左子树边数和右子树边数之和总是最大的，不能纳入递归计数中
    m = max(m, l+r);
	// 左右计数只返回大的
    return max(l, r);
}