`

Google Interview - Longest Continuous Path of Tree

 
阅读更多

给一个树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);
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics