LeetCode-687--最长同值路径--递归

递归"/>

LeetCode-687--最长同值路径--递归

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

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

示例 1:

输入:

          5/ \4   5/ \   \1   1   5

输出:

2

示例 2:

输入:

          1/ \4   5/ \   \4   4   5

输出:

2

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

思路：

1. 获取左子树的最大路径和右子树的最大路径，如果和父节点的值则加一，不相等则最大路径为0。
2. 将处理后的左子树路径和右子树路径相加与全局最大值相比，大于则更新。
3. 将左右子树的最大路劲返回。

代码：

class Solution_687 {int ans;public int longestUnivaluePath(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode root) {if (root == null) {return 0;}//获取左右子树的最大路径int left = dfs(root.left);int right = dfs(root.right);//处理左右子树的路径，不相等则置为0，相等则加1int resLeft = 0, resRight = 0;if (root.left != null && root.left.val == root.val) {resLeft += left + 1;}if (root.right != null && root.right.val == root.val) {resRight += right + 1;}//更新结果ans = Math.max(ans, resLeft + resRight);//返回路径最大值return Math.max(resLeft, resRight);}
}