pylist

614. Binary Tree Longest Consecutive Sequence II

Given a binary tree, find the length(number of nodes) of the longest consecutive sequence(Monotonic and adjacent node values differ by 1) path. The path could be start and end at any node in the tree

Example 1:

Input:
{1,2,0,3}
Output:
4
Explanation:
    1
   / \
  2   0
 /
3
0-1-2-3

Example 2:

Input:
{3,2,2}
Output:
2
Explanation:
    3
   / \
  2   2
2-3

Solution

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the length of the longest consecutive sequence path
    """
    def longestConsecutive2(self, root):
        def dfs(node):
            """
            in:
                node: TreeNode: root of current sub-tree
            out:
                maxLength: int: the longest length of currently seen 
                    consecutive sequence path
                lenIn: int: the length of increasing sequence including the node
                    increasing means child.val + 1 == node.val
                lenDe: int: the length of decreasing sequence including the node
            """
            # if no such node
            if node is None:
                return -float("inf"), 0, 0
            # if leaf
            if node.left is None and node.right is None:
                return 1, 1, 1
            # acquire answers
            maxLength_L, lenIn_L, lenDe_L = dfs(node.left)
            maxLength_R, lenIn_R, lenDe_R = dfs(node.right)
            # combine answers
            ## updata lenIn
            lenIn = 1
            if node.left is not None:
                if node.left.val + 1 == node.val:
                    lenIn = max([lenIn, lenIn_L + 1])
            if node.right is not None:
                if node.right.val + 1 == node.val:
                    lenIn = max([lenIn, lenIn_R + 1])
            ## update lenDe
            lenDe = 1
            if node.left is not None:
                if node.left.val - 1 == node.val:
                    lenDe = max([lenDe, lenDe_L + 1])
            if node.right is not None:
                if node.right.val - 1 == node.val:
                    lenDe = max([lenDe, lenDe_R + 1])
            ## update length
            ### length of a sequense that increase in left subtree 
            ### and decrease in right subtree
            length_Lin_Rde = 1
            if node.left is not None:
                if node.left.val + 1 == node.val:
                    length_Lin_Rde += lenIn_L
            if node.right is not None:
                if node.right.val - 1 == node.val:
                    length_Lin_Rde += lenDe_R
            ### length of a sequense that decrease in left subtree 
            ### and increase in right subtree
            length_Lde_Rin = 1
            if node.left is not None:
                if node.left.val - 1 == node.val:
                    length_Lde_Rin += lenDe_L
            if node.right is not None:
                if node.right.val + 1 == node.val:
                    length_Lde_Rin += lenIn_R
            ## update maxLength
            maxLength = max([maxLength_L,
                             maxLength_R,
                             length_Lin_Rde,
                             length_Lde_Rin])
            # return combined answer
            return maxLength, lenIn, lenDe
        return dfs(root)[0]

special care: