Binary Tree Longest Consecutive Sequence
Description
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.
Hint
Train of Thought
用dfs, 传当前node的值进子节点, 如果是连续的, level就加1, 否则重新变为1, 维护一个max值
Code
public class Solution {
private int max = 1;
public int longestConsecutive(TreeNode root) {
if (root == null ) {
return 0;
}
dfs(root.left, root.val, 1);
dfs(root.right, root.val, 1);
return max;
}
private void dfs(TreeNode root, int val, int level) {
if (root == null) {
return;
}
if (root.val - val == 1) {
level++;
} else {
level = 1;
}
max = Math.max(max, level);
dfs(root.left, root.val, level);
dfs(root.right, root.val, level);
}
}