Binary Tree Longest Consecutive Sequence II

public class Solution {
    int maximumLength = 0;

    public int findLongestConsecutive(TreeNode root) {
        calculateLongest(root);
        return maximumLength;
    }

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

        int increase = 1, decrease = 1;
        if (node.left != null) {
            int[] leftPath = calculateLongest(node.left);
            if (node.val == node.left.val + 1) {
                decrease = leftPath[1] + 1;
            } else if (node.val == node.left.val - 1) {
                increase = leftPath[0] + 1;
            }
        }

        if (node.right != null) {
            int[] rightPath = calculateLongest(node.right);
            if (node.val == node.right.val + 1) {
                decrease = Math.max(decrease, rightPath[1] + 1);
            } else if (node.val == node.right.val - 1) {
                increase = Math.max(increase, rightPath[0] + 1);
            }
        }

        maximumLength = Math.max(maximumLength, increase + decrease - 1);
        return new int[] {increase, decrease};
    }
}

The Java solution provided addresses the problem of finding the longest consecutive sequence in a binary tree, which can either increase or decrease. The approach revolves around implementing a depth-first search (DFS) technique to delve into each node, determine the sequence length, and update the overall maximum accordingly. Here’s a summary of how this solution operates:

1. The class, Solution, includes a method named findLongestConsecutive that begins the traversal from the root node and ultimately returns the maximum length of the longest consecutive sequence.

2. A helper method, calculateLongest, is implemented recursively to navigate through the tree. It accepts a node as an argument and returns an array of two integers representing the lengths of increasing and decreasing sequences from this node.

3. For each node examined, if it has a left child, the algorithm recursively calculates the longest paths for the left subtree. Depending on the node values, it adjusts the increase or decrease values.

4. A similar strategy is applied to the right child of the node.

5. After considering both children, the method calculates the maximum possible length of a consecutive sequence passing through the current node by summing the incremented and decremented lengths (adjusting for double-counting the current node).

6. The method then updates the global maximumLength if the newly computed sequence length surpasses the current known maximum.

7. Finally, the method returns an integer array containing the lengths of the longest increasing and decreasing consecutive sequences available from that node, facilitating the recursive computation for its parent node.

This solution efficiently manages the complex problem of adjusting counts on both the left and right sides while ensuring optimal performance with a recursive depth-first search strategy, making it both effective and elegant for applications that require binary tree manipulation.

class Solution:
    def longestContinuousSequence(self, node: TreeNode) -> int:

        def dfs(current: TreeNode) -> List[int]:
            nonlocal longest_sequence

            if not current:
                return [0, 0]

            increase_run = decrease_run = 1
            if current.left:
                left_vals = dfs(current.left)
                if (current.val == current.left.val + 1):
                    decrease_run = left_vals[1] + 1
                elif (current.val == current.left.val - 1):
                    increase_run = left_vals[0] + 1

            if current.right:
                right_vals = dfs(current.right)
                if (current.val == current.right.val + 1):
                    decrease_run = max(decrease_run, right_vals[1] + 1)
                elif (current.val == current.right.val - 1):
                    increase_run = max(increase_run, right_vals[0] + 1)

            longest_sequence = max(longest_sequence, decrease_run + increase_run - 1)
            return [increase_run, decrease_run]

        longest_sequence = 0
        dfs(node)
        return longest_sequence

This code provides a solution for finding the longest consecutive sequence in a binary tree where sequences can both increase and decrease from parent to children. Using Python, the code employs a recursive depth-first search (DFS) approach to explore each node's potential sequence contributions.

• Define a nested dfs function that:

  • Base case: Returns [0, 0] for a None node indicating no consecutive sequence.
  • For each non-null node, initializes increase_run and decrease_run to 1.
  • Recursively calls itself for left and right children if they exist.
  • Adjusts the increase_run and decrease_run based on the value comparisons with left and right child nodes.
  • Compares and updates the runs when both increasing and decreasing sequences occur.
  • Keeps track of the globally longest sequence encountered during the traversal using the longest_sequence variable.
  • Returns both lengths of increases and decreases as a List[int] for any given node.

• The function longestContinuousSequence:

  • Initializes a nonlocal variable longest_sequence to zero.
  • Invokes the dfs function on the root node to initiate the depth-first traversal.
  • Finally, returns the value of longest_sequence as the length of the longest consecutive sequence that was discovered.

The implementation efficiently computes the combined lengths of consecutive sequences that sequentially increase and decrease through recursive traversal and comparative logic, making it a robust solution for the given problem.