Java Recursive Solution with some comments.


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

  • 1
    Q

    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

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


  • 0
    D

    said in Java Recursive Solution with some comments.:

    ret

    could you please explain every element in ret?
    thanks


  • 0

    @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 "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.


Log in to reply
 

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