298. Binary Tree Longest Consecutive Sequence 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.
public class Solution {
public int longestConsecutive(TreeNode root) {
if(root == null){
return 0;
}
return findLongest(root, 0, root.val - 1); // 初始assume root.val-1 是为了把第一个root加进长度里 root.val-1 和root.val是合法的联系序列
}
private int findLongest(TreeNode root, int length, int preVal){
if(root == null){
return length;
}
// 判断当前是否连续
int currLen = preVal + 1 == root.val ? length + 1 : 1;
// 返回当前长度，左子树长度，和右子树长度中较大的那个
return Math.max(currLen, Math.max(findLongest(root.left, currLen, root.val), findLongest(root.right, currLen, root.val)));
}
}
// version 2: Another Traverse + Divide Conquer
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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) {
return helper(root, null, 0);
}
private int helper(TreeNode root, TreeNode parent, int lengthWithoutRoot) {
if (root == null) {
return 0;
}
int length = (parent != null && parent.val + 1 == root.val)
? lengthWithoutRoot + 1
: 1;
int left = helper(root.left, root, length);
int right = helper(root.right, root, length);
return Math.max(length, Math.max(left, right));
}
}
Ref：