给一个树root的pointer,树包含多个分支,树结构要自己创造。求一条最长路径。
例如(括号对应上面node)
树: 2
| | | |
5 7 3 6
(| | )( | )( | ) (| |)
6 3 2 4 5 8
|
3
返回3因为 (2-3-4) 这条线。优化要求时间O(n)
static class NTreeNode { int val; List<NTreeNode> children = new ArrayList<>(); } public int longestContinuousPath(NTreeNode root) { if(root == null) return 0; return longestContinuousPath(root, 1); } public int longestContinuousPath(NTreeNode root, int len) { int max = 0; for(NTreeNode child:root.children) { if(child == null) continue; int curLen = longestContinuousPath(child, child.val == root.val + 1 ? len + 1 : 1); max = Math.max(curLen, max); } return Math.max(max, len); }
相关推荐
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
北大POJ2533-Longest Ordered Subsequence【O(n^2)】
最长公共子序列演示程序,算法分析与设计,动态规划算法
前端工程师面试
前端工程师面试
java 排序源码
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
The Complexity of Word Circuits.- On the Density of Regular and Context-Free Languages.- Extensions of the Minimum Cost Homomorphism Problem.- The Longest Almost-Increasing Subsequence.- Universal ...
The number of questions is increasing recently. Here is the classification of all `468` questions. For more questions and solutions, you can see my [LintCode](https://github.com/kamyu104/LintCode) ...
自述文件 该自述文件通常会记录启动和运行应用程序所需的所有步骤。 您可能要讲的内容: Ruby版本 系统依赖 配置 数据库创建 数据库初始化 如何运行测试套件 服务(作业队列,缓存服务器,搜索引擎等) ...
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...