Java Recursive Solution with some comments.

  • 1
    int maxlen;
    public int longestConsecutive(TreeNode root) {
        maxlen = 0;
        if(root==null) return maxlen;
        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.
            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]);
            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;

  • 1

    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?

  • 0

    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.

  • 0

    said in Java Recursive Solution with some comments.:


    could you please explain every element in ret?

  • 0

    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

       /   \
     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.

Log in to reply

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