-
Notifications
You must be signed in to change notification settings - Fork 21
/
Binary Tree Longest Consecutive Sequence.java
executable file
·150 lines (133 loc) · 4.13 KB
/
Binary Tree Longest Consecutive Sequence.java
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
M
1527054989
tags: Tree, DFS, Divide and Conquer
找到binary tree 里的最长 consecutive sequence.
#### DFS
- Divide and Conquer. dfs
- 分开 看左边/右边
- 如果左边满足连续递增的规则, dfs (depth + 1), 如果不满足规则, dfs(depth = 1)
- 右边也是一样
- 对结果跟max作比较, return
```
/*
Given a binary tree, find the length of the longest consecutive sequence path.
The path refers to any sequence of nodes from some starting node to any node in the tree
along the parent-child connections. The longest consecutive path need to be from parent to child
(cannot be the reverse).
For example,
1
\\
3
/ \\
2 4
\\
5
Longest consecutive sequence path is 3-4-5, so return 3.
2
\\
3
/
2
/
1
Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
Tags:Tree
Similar Problems: (H) Longest Consecutive Sequence
*/
/*
Thoughts:
1. Mark depth at each level
2. discuss wether extend or start new depth (per problem requirement)
*/
class Solution {
public int longestConsecutive (TreeNode root) {
if (root == null) {
return 0;
}
return dfs(root, 1);
}
private int dfs(TreeNode node, int depth) {
if (node == null) {
return depth;
}
// check node
int leftDepth = (node.left != null && node.val + 1 == node.left.val) ?
dfs(node.left, depth + 1) : dfs(node.left, 1);
int rightDepth = (node.right != null && node.val + 1 == node.right.val) ?
dfs(node.right, depth + 1) : dfs(node.right, 1);
return Math.max(depth, Math.max(leftDepth, rightDepth));
}
}
/*
// DFS, actually find all the items in rst: List<List<Integer>>. It's not requried in this problem.
public class Solution {
public int longestConsecutive(TreeNode root) {
if (root == null) {
return 0;
}
List<List<Integer>> rst = new ArrayList<>();
dfs(rst, new ArrayList<>(), root);
List<Integer> list = new ArrayList<>();
for (List<Integer> candidate: rst) {
list = candidate.size() > list.size() ? candidate : list;
}
return list.size();
}
private void dfs(List<List<Integer>> rst,
List<Integer> list,
TreeNode node) {
if (node == null) {
if (list != null && list.size() > 0) {
rst.add(new ArrayList<>(list));
}
return;
}
// check node
if (list.size() > 0 && list.get(list.size() - 1) != node.val - 1) {
rst.add(new ArrayList<>(list));
dfs(rst, new ArrayList<>(), node);
} else {
list.add(node.val);
dfs(rst, list, node.left);
dfs(rst, list, node.right);
list.remove(list.size() - 1);
}
}
}
*/
/*
Attemp2: http://www.cnblogs.com/jcliBlogger/p/4923745.html.
The original solution has just 4 lines of C++ code. That hurts.
The concept is very much similar as my attempt1, though the code is more clear with recursive call
1. pass alone a depth.
2. if consecutive, depth++; else, start from depth 1
3. Go deeper on both left, and right; both with new depth: currDepth;
4. Compare the Max of currDept, left's return, right's return.
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int longestConsecutive(TreeNode root) {
return recursiveHelper(root, null, 0);
}
public int recursiveHelper(TreeNode curr, TreeNode parent, int depth) {
if (curr == null) {
return 0;
}
int currDepth = 0;
if (parent != null && parent.val + 1 == curr.val) {
currDepth = depth + 1;
} else {
currDepth = 1;
}
return Math.max(currDepth, Math.max(recursiveHelper(curr.left, curr, currDepth), recursiveHelper(curr.right, curr, currDepth)));
}
}
```