549. Binary Tree Longest Consecutive Sequence II

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

Input:
        1
       / \
      2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

Input:
        2
       / \
      1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Note: All the values of tree nodes are in the range of [-1e7, 1e7].

Greedy:

class Solution {
 public :
     int longestConsecutive (TreeNode * root) {
         if (! root) return  0 ;
         int res = helper (root, 1 ) + helper (root, -1 ) + 1 ;
         return max (res, max (longestConsecutive ( root-> left), longestConsecutive (root-> right)));
    }
    int helper (TreeNode * node, int diff) {
         if (! node) return  0 ;
         int left = 0 , right = 0 ;
         if (node-> left && node-> val-node-> left-> val == diff ) {
            left = 1 + helper (node-> left, diff);
        }
        if (node-> right && node-> val-node-> right-> val == diff) {
            right = 1 + helper (node-> right, diff);
        }
        return max (left, right);
    }
};

Approach #2 Single traversal [Accepted]

Algorithm

This solution is very simple. With every node, we associate two values/variables named $inr$and $dcr$, where $incr$ represents the length of the longest incrementing branch below the current node including itself, and $dcr$ represents the length of the longest decrementing branch below the current node including itself.

We make use of a recursive function longestPath(node) which returns an array of the form $[inr, dcr]$ for the calling node. We start off by assigning both $inr$ and $dcr$ as 1 for the current node. This is because the node itself always forms a consecutive increasing as well as decreasing path of length 1.

Then, we obtain the length of the longest path for the left child of the current node using longestPath[root.left]. Now, if the left child is just smaller than the current node, it forms a decreasing sequence with the current node. Thus, the $dcr$ value for the current node is stored as the left child's $dcr$ value + 1. But, if the left child is just larger than the current node, it forms an incrementing sequence with the current node. Thus, we update the current node's $inr$ value as $left\_child(inr) + 1$.

Then, we do the same process with the right child as well. But, for obtaining the $inr$ and $dcr$value for the current node, we need to consider the maximum value out of the two values obtained from the left and the right child for both $inr$ and $dcr$, since we need to consider the longest sequence possible.

Further, after we've obtained the final updated values of $inr$ and $dcr$ for a node, we update the length of the longest consecutive path found so far as $maxval = \text{max}(inr + dcr - 1)$.

The following animation will make the process clear:

6 / 16

Complexity Analysis

• Time complexity : $O(n)$. The whole tree is traversed only once.
• Space complexity : $O(n)$. The recursion goes upto a depth of $n$ in the worst case.