Google Interview - Longest Continuous Path of Tree - 我的博客 - ITeye技术网站

Google Interview - Longest Continuous Path of Tree - 我的博客 - ITeye技术网站
给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长路径。
例如（括号对应上面node）
树：                  2
      |            |            |                |
     5            7          3                 6
（|       | ）（ | ）（ | ）        （|       |）
  6       3        2         4              5       8
                     |
                     3
返回3因为 （2-3-4） 这条线。优化要求时间O(n)

1. static class NTreeNode {  
2.     int val;  
3.     List<NTreeNode> children = new ArrayList<>();  
4. }  
5.   
6. public int longestContinuousPath(NTreeNode root) {  
7.     if(root == null) return 0;  
8.     return longestContinuousPath(root, 1);  
9. }  
10.   
11. public int longestContinuousPath(NTreeNode root, int len) {  
12.     int max = 0;  
13.     for(NTreeNode child:root.children) {  
14.         if(child == null) continue;  
15.         int curLen = longestContinuousPath(child, child.val == root.val + 1 ? len + 1 : 1);  
16.         max = Math.max(curLen, max);  
17.     }  
18.     return Math.max(max, len);  
19. }

Read full article from Google Interview - Longest Continuous Path of Tree - 我的博客 - ITeye技术网站