-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathbtlongestConSeqII.java
More file actions
45 lines (43 loc) · 1.51 KB
/
btlongestConSeqII.java
File metadata and controls
45 lines (43 loc) · 1.51 KB
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Arrays;
public class btlongestConSeqII {
public static void main(String[] args){
Codec obj = new Codec();
String data = "1,2,3,N,N,N,N,";
TreeNode root = obj.deserilize2(data);
btlongestConSeqII obj2 = new btlongestConSeqII();
System.out.println(obj2.longest(root));
}
// top down then bottom up. O(n) time
// 遍历同时打擂台
int max;
public int longest(TreeNode root){
max = 0;
dfs(root);
return max;
}
// return int[]: longest increasing and longest decreasing
private int[] dfs(TreeNode root){
if(root == null) return new int[]{0,0};
int[] left = dfs(root.left);
int[] right = dfs(root.right);
int[] cur = new int[] {1,1};
if(root.left!=null && (root.left.val == root.val+1 || root.left.val == root.val-1)){
if(root.left.val > root.val){
cur[1] = Math.max(left[1]+1, cur[1]);
}else{
cur[0] = Math.max(left[0]+1, cur[0]);
}
}
if(root.right!=null && (root.right.val == root.val+1 || root.right.val == root.val-1)){
if(root.right.val > root.val){
cur[1] = Math.max(right[1]+1, cur[1]);
}else{
cur[0] = Math.max(right[0]+1, cur[0]);
}
}
System.out.println("root:" + root.val);
System.out.println("int[]: " + Arrays.toString(cur));
max = Math.max(max, cur[0]+cur[1]-1);
return cur;
}
}