Java Binary Tree Longest Consecutive Sequence with explanation


  • 3
    V

    To find the longest consecutive sequence, we need to record three things: the previous node's value, an int value for the current path length, and an int value for the longest sequence length.

    I set these three variables as preVal, localLen, retLen.

    The idea is that, if the current node's value is equals to preVal + 1, it indicts that it is consecutive, so we update the localLen by adding 1, and update the retLen, to maintain max length in the retLen; if not equal, we just need to treat this node as a new start point of a next consecutive sequence, so we set localLen to 1, and no need to update retLen.

    public class Solution {

    public int longestConsecutive(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        return Math.max(longest(root.left, 1, 1, root.val), longest(root.right, 1, 1, root.val));
    }
    
    public int longest(TreeNode root, int localLen, int retLen, int preVal){
        if(root == null){
            return retLen;
        }
        
        if(root.val == preVal + 1){
            localLen++;
            retLen = Math.max(localLen, retLen);
        }else{
            localLen = 1;
        }
        
        return Math.max(longest(root.left, localLen, retLen, root.val), longest(root.right, localLen, retLen, root.val));
    }
    

    }


  • 0
    V

    Also I think the time complexity is O(n), because it will manipulate every node of the tree, am I correct ?


Log in to reply
 

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