public class Solution {
public int longestConsecutive(TreeNode root) {
return (root==null)?0:Math.max(dfs(root.left, 1, root.val), dfs(root.right, 1, root.val));
}
public int dfs(TreeNode root, int count, int val){
if(root==null) return count;
count = (root.val  val == 1)?count+1:1;
int left = dfs(root.left, count, root.val);
int right = dfs(root.right, count, root.val);
return Math.max(Math.max(left, right), count);
}
}
Simple Recursive DFS without global variable


@chuR maybe that means if you want to examine another tree root, you should initialize a new object of class Solution. Because a global var max would influence this.

@Jrui well, you can actually reset the global variable before return. I think this problem is perfect to use instance variable.
int tmp = this.max;
this.max = 0;
return tmp;

My another approach is to take max of the length till now and the max of left and right length. Following is the simple implementation :
public int longestConsecutive(TreeNode root) { if(root == null) return 0; return longestConsecutive(root, null, 0); } public int longestConsecutive(TreeNode root, TreeNode prev, int len) { if(root == null) return len; // reached the leaf node. int leftLen = 0, rightLen = 0; if(prev != null && root.val == prev.val + 1) { // Increasing node found leftLen = longestConsecutive(root.left, root, len + 1); rightLen = longestConsecutive(root.right, root, len + 1); } else { // This node breaks the increasing property. So start again from here. leftLen = Math.max(len, longestConsecutive(root.left, root, 1)); rightLen = Math.max(len, longestConsecutive(root.right, root, 1)); } return Math.max(leftLen, rightLen); }

Same idea. My python code.
class Solution(object): def longestConsecutive(self, root): def _dfs(node, parent, cur_l): if not node: return cur_l if parent == None or node.val != parent + 1: cur_l = 0 cur_l += 1 return max(_dfs(node.left, node.val, cur_l), _dfs(node.right, node.val, cur_l), cur_l) return _dfs(root, None, 0)

Similar idea but there is no need to separate the recursion for left and right nodes in the main function
public int longestConsecutive(TreeNode root) { if(root == null) return 0; int res = dfs(root, 1, root.val); return res; } private int dfs(TreeNode node, int count, int prev) { if(node == null) return count; if(node.val == prev + 1) count ++; else count = 1; int left = dfs(node.left, count, node.val); int right = dfs(node.right, count, node.val); return Math.max(Math.max(left,right), count); }

@Anylnb I really like your solution, its clean and simple. Keep it up.
I came up with this solution. Here I am passing the currentCount and the maxCount at each step.public int longestConsecutive(TreeNode root){ return helper(root, null, 0, 0); } private int helper(TreeNode root, TreeNode prev, int cnt, int mx){ if (null == root){ return Math.max(cnt, mx); } if (null != prev && root.val  1 == prev.val) { cnt++; }else { mx = Math.max(cnt, mx); cnt = 1; } int left = helper(root.left, root, cnt, mx); int right = helper(root.right, root, cnt, mx); return Math.max(left, right); }

Make it more simplified. public int longestConsecutive(TreeNode root) { if(root==null) return 0; return Helper(root, 1, root.val); } public int Helper(TreeNode root, int count, int val){ if(root==null) return count; count = (root.val  val == 1)?count+1:1; int left = Helper(root.left, count, root.val); int right = Helper(root.right, count, root.val); return Math.max(Math.max(left, right), count); }