BiruLyu
6/7/2017 - 12:17 AM

## 298. Binary Tree Longest Consecutive Sequence(1st).java

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int maxLen = 0;
public int longestConsecutive(TreeNode root) {
int cur = opt(root);
return Math.max(maxLen, cur); // [1]
}

private int opt(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return 1;
int left = opt(root.left);
int right = opt(root.right);

int res = 1;

if(left > 0 && right > 0 && root.left.val - 1 == root.val && root.right.val - 1 == root.val) {
res += Math.max(left, right);
} else if (left > 0 && root.left.val - 1 == root.val) {
res += left;
} else if(right > 0 && root.right.val - 1 == root.val) {
res += right;
}
maxLen = Math.max(maxLen, res);
return res;
}

}

/*
*/``````
``````/**
* 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) {
if(root == null) return 0;

return longestConsecutive(root, root.val - 1, 0, 0);
}
public int longestConsecutive(TreeNode node, int prev, int sum, int maxsum){
if(node == null) return Math.max(maxsum, sum);

if(node.val == prev + 1){
sum += 1;
}else{
sum = 1;
}
maxsum = Math.max(maxsum, sum);

return Math.max(
longestConsecutive(node.left,  node.val, sum, maxsum),
longestConsecutive(node.right, node.val, sum, maxsum));
}
}``````