Longest Univalue Path——LeetCode进阶路
生活随笔
收集整理的这篇文章主要介绍了
Longest Univalue Path——LeetCode进阶路
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
原题链接https://leetcode.com/problems/longest-univalue-path
题目描述
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.
思路分析
返回给定二叉树的相同节点值的最长路径，不一定要从根节点开始，且长度以节点之间的边数表示。
对于某个节点
- 递归计算左右子树的最大长度
- 更新当前最大长度
- 若左右子树的根节点的值等于当前节点值的话，取大者
All in all,很友好的题，但是我写题解&&做题的时间超时了……
AC解
/**
* 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 longestUnivaluePath(TreeNode root) {
if(root == null)
{
return 0;
}
dfs(root,0);
return res;
}
public int dfs(TreeNode root,int curVal)
{
if(root == null)
{
return 0;
}
int left = (root.left != null) ? dfs(root.left,root.val) : 0;
int right = (root.right != null) ? dfs(root.right,root.val) : 0;
res = Math.max(res,left + right);
return (curVal == root.val) ? (Math.max(left,right)+1) : 0;
}
}
总结
以上是生活随笔为你收集整理的Longest Univalue Path——LeetCode进阶路的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 腾讯出品！这款Markdown神器让你码
- 下一篇： 自定义Spring Authorizat