[Leetcode] 549. Binary Tree Longest Consecutive Sequence II

I am quite happy to solve this problem on my own. Let me explain in a little bit more detailed way.

Tl;dr: recursion; construct a function that can pass the information about the subtrees as well as the global result

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].

---

This problem reminds me of a famous dynamic programming example, longest increasing sequencing, in which we construct the final result from subproblems. If I have a way to traverse the tree as we scan the array, if we are given a node and its left subtree's longest consecutive sequence length (CSL), right subtree's CSL, of course its left node and right node, we should be able to reason about my current node's longest consecutive sequence. Therefore, this problem can also be framed as dynamic programming problem. However, tree's traversal is way more indirect - we have to be comfortable with recursion.

Here comes the function "design" part, if we only save the local result, i.e., my current node's CSL, since my current node may not involve in the final solution, we won't be able to retrieve the final solution. Hence, we should also save the best result up to current node.

Also, the sequence can increase or decrease, and the path can be children-parent-children, and think about if we have a left_child - parent - right_child path, obviously, parent to left child and parent to right child are not in the same direction (increase-decrease or decrease-increase). Therefore, we also need to pass the increase, decrease information. Why not all then?

Together, the code (longer than most of Leetcode problem. indeed, the final if statements are quite tricky, have to be careful.)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def longestConsecutive(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = [0]
        self.helper(root, res)
        return res[0]
    
    def helper(self, node, res):
        if not node:
            return 0, 0
        elif not node.left and not node.right:
            res[0] = max(1, res[0])
            
            return 1, 1
        else:
            l_in, l_de = self.helper(node.left, res)
            r_in, r_de = self.helper(node.right, res)
            
            ret_in, ret_de = 1, 1 # return to next level
            
            tmp_res = 1 # children_parent_children pair
            
            if node.left:
                if node.left.val == node.val - 1:
                    # increase
                    ret_in = max(ret_in, l_in + 1)
                if node.left.val == node.val + 1:
                    # decrase
                    ret_de = max(ret_de, l_de + 1)
            if node.right:
                if node.right.val == node.val - 1:
                    # increase
                    ret_in = max(ret_in, r_in + 1)
                if node.right.val == node.val + 1:
                    # decrase
                    ret_de = max(ret_de, r_de + 1)
            if node.left and node.right:
                if node.left.val == node.val-1 == node.right.val-2:
                    tmp_res = max(tmp_res, l_in + 1 + r_de)
                if node.left.val == node.val + 1 == node.right.val + 2:
                    tmp_res = max(tmp_res, l_de + 1 + r_in)
            res[0] = max(tmp_res, ret_in, ret_de, res[0])
            return ret_in, ret_de