Both iterative and recursive methods with explanations


  • 4
    E

    Iterative method is quite straightforward: use BFS and update max level by level until reaching the bottom level. One detail is that I used another queue q2 to store the length of the sequence ending at current node.

    Code in Java:

    public int longestConsecutive(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        q.add(root);
        q2.add(1);
        int max = 1;
        while(!q.isEmpty()) {
            int size = q.size();
            for(int i=0; i<size; i++) {
                TreeNode current = q.poll();
                int count = q2.poll();
                if(current.left!=null) {
                    q.add(current.left);
                    if(current.left.val == current.val+1) {
                        q2.add(count+1);
                        max = count+1 > max ? count+1 : max;
                    }
                    else
                        q2.add(1);
                }
                if(current.right!=null) {
                    q.add(current.right);
                    if(current.right.val == current.val+1) {
                        q2.add(count+1);
                        max = count+1 > max ? count+1 : max;
                    }
                    else
                        q2.add(1);
                }
            }
        }
        return max;
    }
    

    For recursive method, the key is to use a state variable max that stores the global maximum length of all subtrees.

    Code in Java:

    private int max;
    public int longestConsecutive(TreeNode root) {
        if(root==null) return 0;
        max = 1;
        helper(root, 1);
        return max;
    }
    private void helper(TreeNode root, int maxCurrent) {
        if(root==null) return;
        if(root.left!=null) {
            if(root.left.val == root.val+1) {
                max = maxCurrent+1 > max ? maxCurrent+1 : max;
                helper(root.left, maxCurrent+1);
            }
            else
                helper(root.left, 1);
        }
        if(root.right!=null) {
            if(root.right.val == root.val+1) {
                max = maxCurrent+1 > max ? maxCurrent+1 : max;
                helper(root.right, maxCurrent+1);
            }
            else
                helper(root.right, 1);
        }
        
    }

Log in to reply
 

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