LeetCode 549: Binary Tree Longest Consecutive Sequence II Solution

Master LeetCode problem 549 (Binary Tree Longest Consecutive Sequence II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

549. Binary Tree Longest Consecutive Sequence II

Medium

Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

This problem asks us to find the longest consecutive sequence in a binary tree. The consecutive sequence can be either increasing or decreasing, but the nodes have to be in the same order as in the root-to-leaf paths.

To solve this problem, we can use a recursive approach where we pass the current node, the length of the increasing sequence ending at the current node, and the length of the decreasing sequence ending at the current node. At each node, we compare the node's value with its children to determine if we can extend the consecutive sequences.

Here are the steps for the algorithm:

Define a recursive function that takes the current node, the length of increasing sequence ending at the current node, and the length of decreasing sequence ending at the current node.
Base case: If the current node is null, return a pair of (0, 0) representing the length of increasing and decreasing sequences as 0.
Recursively call the function on the left and right children of the current node.
Determine if we can extend the increasing and decreasing sequences at the current node based on its value and the values of its children.
Update the maximum length of the consecutive sequence found so far.
Return a pair of the length of increasing sequence and the length of decreasing sequence ending at the current node.

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. The space complexity is O(N) as well for the recursive stack.

Solution Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    int maxLen = 0;

    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        helper(root);
        return maxLen;
    }

    private int[] helper(TreeNode node) {
        if (node == null) return new int[]{0, 0};

        int inc = 1, dec = 1;
        if (node.left != null) {
            int[] left = helper(node.left);
            if (node.val == node.left.val + 1)
                inc = left[0] + 1;
            else if (node.val == node.left.val - 1)
                dec = left[1] + 1;
        }
        if (node.right != null) {
            int[] right = helper(node.right);
            if (node.val == node.right.val + 1)
                inc = Math.max(inc, right[0] + 1);
            else if (node.val == node.right.val - 1)
                dec = Math.max(dec, right[1] + 1);
        }

        maxLen = Math.max(maxLen, inc + dec - 1);
        return new int[]{inc, dec};
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 549 (Binary Tree Longest Consecutive Sequence II)?

This page provides optimized solutions for LeetCode problem 549 (Binary Tree Longest Consecutive Sequence II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 549 (Binary Tree Longest Consecutive Sequence II)?

The time complexity for LeetCode 549 (Binary Tree Longest Consecutive Sequence II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 549 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 549 in Java, C++, or Python.

Back to LeetCode Solutions