[LeetCode] 687. Longest Univalue Path

本文主要是介绍[LeetCode] 687. Longest Univalue Path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/longest-univalue-path/description/

题目

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.

题目大意

相同结点值路径的最大长度

思路

相同结点值路径的最大长度res = 左子树中 结点都在不同层的 相等路 的结点数 + 右子树中 结点都在不同层的相等路 的结点数 + 1 - 1 。
最后减1是因为 边的数 == 结点数 - 1。

问题转化为：
求 结点作为root， 结点都在不同层相等路 的 结点数。

dfs 递归方法

int dfs(TreeNode) 递归函数状态：返回 左右子树中 较长 结点都在不同层的相等路 的长度（结点数）。

状态转移方程：
1.dfs(root) = max(dfs(root.left),dfs(root.right)) +1（若当前结点的val 与 子树结点的相同）

2.dfs(root) = dfs(root.left) + 1 （若只有 左子树 存在且相同）

3.dfs(root) = 1 (若都子树都不存在 或 子树结点val与root不同)

终止条件：if root == null，return 0；

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {int res = 0;public int dfs(TreeNode root){if(root == null)return 0;int lPathLenth = dfs(root.left);int rPathLenth = dfs(root.right);if(!(root.left!=null && root.left.val == root.val))lPathLenth = 0;if(!(root.right!=null && root.right.val == root.val))rPathLenth = 0;res = Math.max(res,lPathLenth + rPathLenth);return Math.max(lPathLenth,rPathLenth) + 1;}public int longestUnivaluePath(TreeNode root) {dfs(root);return res;}
}

这篇关于[LeetCode] 687. Longest Univalue Path的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---