1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
private int ans = 0;
public int longestConsecutive(TreeNode root) {
helper(root);
return ans;
}
private int helper(TreeNode node) {
if (node == null) {
return 0;
}
int leftTreeStreak = helper(node.left);
int rightTreeStreak = helper(node.right);
int currStreak = 1;
if (node.left != null && node.val + 1 == node.left.val) {
currStreak = Math.max(currStreak, leftTreeStreak + 1);
}
if (node.right != null && node.val + 1 == node.right.val) {
currStreak = Math.max(currStreak, rightTreeStreak + 1);
}
ans = Math.max(ans, currStreak);
return currStreak;
}
}
|
也是让每个node都当头, 看看能组成的sequence有多长. 递归函数的功能就是告诉我们某个node作为头的时候, 最长的sequence是多少.
时间复杂度: O(n)
空间复杂度: O(n)
