[LeetCode] 549. Binary Tree Longest Consecutive Sequence II

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

Assume we only construct increasing consecutive sequence. So a new node value can append to a sequence in below 3 scenarios:

[new value] xxxxx : add to the start position

xxxxx [new value] : add to the end position

xxxxx [new value] xxxxx : add to the middle of sequence from the left and right subtree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestConsecutive(self, root: TreeNode) -> int:
        self.result = 0
        
        def postorder(node):
            """
            return (s, e)
            s : the length of the longest sequence which starts with 'node'
            e : the length of the longest sequence which ends by 'node'
            """
            
            if node.left and node.right:
                ls, le = postorder(node.left)
                rs, re = postorder(node.right)
                s = e = 1
                
                if node.left.val + 1 == node.val and node.val + 1 == node.right.val:
                    self.result = max(self.result, le + 1 + rs)
                    
                    s = max(s, rs + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val and node.val - 1 == node.right.val:
                    self.result = max(self.result, ls + 1 + re)
                    
                    s = max(s, ls + 1)
                    e = max(e, re + 1)
                
                if node.left.val + 1 == node.val:
                    self.result = max(self.result, le + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val:
                    self.result = max(self.result, ls + 1)
                    s = max(s, ls + 1)
                
                if node.right.val + 1 == node.val:
                    self.result = max(self.result, re + 1)
                    e = max(e, re + 1)
                
                if node.right.val - 1 == node.val:
                    self.result = max(self.result, rs + 1)
                    s = max(s, rs + 1)
            
                return s, e
            
            if node.left:
                ls, le = postorder(node.left)
                s = e = 1
                
                if node.left.val + 1 == node.val:
                    self.result = max(self.result, le + 1)
                    e = max(e, le + 1)
                
                if node.left.val - 1 == node.val:
                    self.result = max(self.result, ls + 1)
                    s = max(s, ls + 1)
                
                return s, e
            
            if node.right:
                rs, re = postorder(node.right)
                s = e = 1
                
                if node.right.val + 1 == node.val:
                    self.result = max(self.result, re + 1)
                    e = max(e, re + 1)
                
                if node.right.val - 1 == node.val:
                    self.result = max(self.result, rs + 1)
                    s = max(s, rs + 1)
                    
                return s, e
            
            self.result = max(self.result, 1)
            return 1, 1
        
        
        postorder(root)
        
        return self.result