Leetcode 0549 Binary Tree Longest Consecutive Sequence II

Problem statement

https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/

Solution

Use helper dfs function, which for every node returns two values: length of longest path, starting from this node and going down, which is decreasing monotonic and second value is for increasing monotonic. If we reached None, return (0, 0). For every node check it children and update lengths = [smaller, bigger] list. Be careful to use lengths[0] = max(lengths[0], 1 + smaller), not just lengths[0] = 1 + smaller, because we can have two children with the same value and we need to choose the best one. Also we update self.maxlen.

Complexity

Time complexity is O(n), space complexity is O(h).

Code

class Solution:
    def longestConsecutive(self, root):
        self.maxlen = 1
        def dfs(node):
            lengths = [0, 0]
            for child in filter(None, [node.left, node.right]):
                [smaller, bigger] = dfs(child)
                if child.val == node.val - 1:
                    lengths[0] = max(lengths[0], 1 + smaller)
                elif child.val == node.val + 1:
                    lengths[1] = max(lengths[1], 1 + bigger)
            
            self.maxlen = max(self.maxlen, lengths[0] + lengths[1] + 1)
            return lengths

        dfs(root)
        return self.maxlen