687.最长同值路径

一、题目概述

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

          5
         / \
        4   5
       / \   \
      1   1   5

输出:

2
示例 2:

输入:

          1
         / \
        4   5
       / \   \
      4   4   5

输出:

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

二、解题方案

思路：采用递归的方法

• 将该二叉树的每个节点都当作根节点；
• 专门写一个递归函数(arrowLength)，参数为节点指针，返回值为子节点最大的同值路径
• 声明一个全局变量(ans)，在递归函数中与结点指针对应的同值路径比较，更新ans
• 递归函数首先依次递归二叉树的所有节点，遇到叶子节点则返回0，如果遇到非叶子节点，比较左右子节点，若存在左、右子节点且值等于根节点值，则同值路径+1，左右同值路径之和与ans相加取其较大的值，返回左右同值路径中较大的值。

	int ans;
	int longestUnivaluePath(TreeNode* root) {
		ans = 0;
		if (root == NULL) return 0;//若为空树则直接返回0
		arrowLength(root);
		return ans;
	}
	int arrowLength(TreeNode* root) {
		//递归到叶子节点 则返回 0
		if (root == NULL) return 0;

		int left = 0, right = 0;
		//递归左右子节点 返回路径数
		int leftArrow = arrowLength(root->left);
		int rightArrow = arrowLength(root->right);
		//若子节点存在且与根节点相等
		if (root->left != NULL && root->val == root->left->val) {
			left = leftArrow + 1;
		}
		if (root->right != NULL && root->val == root->right->val) {
			right = rightArrow + 1;
		}
		ans = ans > (left + right) ? ans : (left + right);
		return left > right ? left : right;
	}