int maxlen;
public int longestConsecutive(TreeNode root) {
maxlen = 0;
if(root==null) return maxlen;
incdecPath(root);
return maxlen;
}
private int[] incdecPath(TreeNode curr){
int[] ret = {1,1,1,1}; // index 0 and 1 used to record from current node to left node. index 0 used to record the length pointing from current node to current.left.
//Of course, you can use a 2D array here using positive and negative numbers to mark the "flow" direction.
if(curr.left!=null){
int[] leftchild = incdecPath(curr.left);
if(curr.val  curr.left.val == 1){
ret[0] += Math.max(leftchild[0], leftchild[2]);
}
if(curr.val  curr.left.val == 1){
ret[1] += Math.max(leftchild[1], leftchild[3]);
}
}
if(curr.right!=null){
int[] rightchild = incdecPath(curr.right);
if(curr.val  curr.right.val == 1){
ret[2] += Math.max(rightchild[0], rightchild[2]);
}
if(curr.val  curr.right.val == 1){
ret[3] += Math.max(rightchild[1], rightchild[3]);
}
}
maxlen = Math.max(maxlen,Math.max(ret[0] + ret[3], ret[1] + ret[2])  1);
return ret;
}
Java Recursive Solution with some comments.


We have the very similar idea. For the array of subroutine, I return array of length 3.
This first entry record: length of the longest increasing sequence ended at this node.
The second entry record: length of the longest decreasing sequence ended at this node.
The third entry record: length of the longest sequence passed this node.
Will this change make the solution better or worse?

@qswawrq
I do not think the time complexity will change. The good thing of your solution is you save one less number. The run time should be similar.

said in Java Recursive Solution with some comments.:
ret
could you please explain every element in ret?
thanks

@DaddyYang
I used sort of flow idea, you can treat the node with lower value as a source and the node with higher value as a sink. Just pick one flow direction you like.
I used ret[] to store the "inflow" and "outflow" from the current node to its left/ right child. That is {left inflow, left outflow, right inflow, right outflow}.
For example, if there is only one single node, ret[] = {1,1,1,1}.
If the tree is2 / \ 1 3
Both node 1 and 3 return ret[] = {1,1,1,1}.
Since node 2's value is bigger than 1, node 2's ret[1] = 1 + node 1's max "inflow".
The inflow and outflow going through the current node in different directions (left child > current node > right child or the other direction) is the path going through the current node. Compare this path's length with the current max length to get the result. As I said in the comment, you can just use a length2array to store the flows using positive and negative value to mark if it is an inflow or outflow. The reason I used length4array because it is easier to tell.