BinarySearch 0453 Binary Tree Longest Consecutive Path

Problem statement

https://binarysearch.com/problems/Binary-Tree-Longest-Consecutive-Path/

Solution

Equal to Leetcode 0549 Binary Tree Longest Consecutive Sequence II.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(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