# Java Recursive Solution with some comments.

• ``````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;
}``````

• 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.

• ret

could you please explain every element in ret?
thanks

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 "in-flow" and "out-flow" from the current node to its left/ right child. That is {left in-flow, left out-flow, right in-flow, right out-flow}.
For example, if there is only one single node, ret[] = {1,1,1,1}.
If the tree is

``````     2
/   \
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 "in-flow".
The in-flow and out-flow 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 length-2-array to store the flows using positive and negative value to mark if it is an in-flow or out-flow. The reason I used length-4-array because it is easier to tell.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.