描述
給一棵二叉樹贮尉，找到最長連續(xù)路徑的長度异雁。
這條路徑是指 任何的節(jié)點序列中的起始節(jié)點到樹中的任一節(jié)點都必須遵循 父-子 聯(lián)系舌仍。最長的連續(xù)路徑必須是從父親節(jié)點到孩子節(jié)點（不能逆序）着绊。
樣例
舉個例子：
1
\
3
/ \
2 4
\
5
最長的連續(xù)路徑為 3-4-5铆隘，所以返回 3加派。
2
\
3
/
2
/
1
最長的連續(xù)路徑為 2-3 ,而不是 3-2-1 叫确，所以返回 2。
返回
[
[1, 2, 2],
[1, 4]
]
代碼
- Traverse + Divide Conquer
自底向上芍锦，復雜度分析
時間復雜度： O(n)O(n) 竹勉。
時間復雜度與后續(xù)遍歷二叉樹一樣都是 O(n)O(n) 。
空間復雜度： O(n)O(n) 娄琉。
遞歸在調(diào)用棧的時候會使用額外的空間次乓。對于一棵嚴重偏斜的二叉樹，遞歸的深度最多達到 nn 層孽水。
public class Solution {
private int longest;
/**
* @param root the root of binary tree
* @return the length of the longest consecutive sequence path
*/
public int longestConsecutive(TreeNode root) {
longest = 0;
helper(root);
return longest;
}
// 包含當前 root 結(jié)點的最長連續(xù)序列
private int helper(TreeNode root) {
// 葉子節(jié)點
if (root == null) {
return 0;
}
int left = helper(root.left);
int right = helper(root.right);
// 每一次遞歸都要重新置 1, 至少包含當前結(jié)點
int subtreeLongest = 1;
// 能和左兒子的連續(xù)序列連上票腰，長度從 1 更新為 left+1
if (root.left != null && root.val + 1 == root.left.val) {
subtreeLongest = Math.max(subtreeLongest, left + 1);
}
if (root.right != null && root.val + 1 == root.right.val) {
subtreeLongest = Math.max(subtreeLongest, right + 1);
}
if (subtreeLongest > longest) {
longest = subtreeLongest;
}
return subtreeLongest;
}
}
