LWC 52：687. Longest Univalue Path
LWC 52：687. Longest Univalue Path
用户1147447
发布于 2018-01-02 10:51:06
发布于 2018-01-02 10:51:06
文章被收录于专栏：机器学习入门
LWC 52：687. Longest Univalue Path
传送门：687. Longest Univalue Path
Problem:
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 5Output: 2
Example 2:
Input:
1
/ \
4 5
/ \ \
4 4 5Output: 2
Note:
The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.
思路： 此题的trick在于如何划分子问题，首先对于原问题的划分如下：
如果最长path经过根节点，则计算出来
否则，分别从左子树和右子树中找出最长路径（不经过根节点）
接下来，只需要计算从某个根结点出发，分别链接左子树的最大路径长度和右子树的最大路径长度。
此处的原问题划分如下：
计算左子树的最大长度
计算右子树的最大长度
如果左右子树根节点的val和它们的父结点val相同，则取其中长度最大的。
代码如下：
public int longestUnivaluePath(TreeNode root) {
if (root == null) return 0;
int val = root.val;
int res = 0;
if (root.left != null && root.left.val == val) {
res = 1 + dfs(root.left);
}
if (root.right != null && root.right.val == val) {
res += 1 + dfs(root.right);
}
return Math.max(res, Math.max(longestUnivaluePath(root.left), longestUnivaluePath(root.right)));
}
public int dfs(TreeNode root) {
if (root == null) return 0;
int res = 0;
int val = root.val;
if (root.left != null && root.left.val == val) {
res = 1 + dfs(root.left);
}
if (root.right != null && root.right.val == val) {
res = Math.max(res, 1 + dfs(root.right));
}
return res;
} 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-10-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
