298.Binary Tree Longest Consecutive Sequence

Tags: [tree], [binary_tree], [consecutive], [consecutive_sequence], [extend_meaning], [BFS], [DFS]

Com: {g}

Link: https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/#/description

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is3-4-5, so return3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is2-3,not3-2-1, so return2.

Solution: Extend Meaning, Extend Function Meaning

# 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
        """
        lc, _ = self.helper(root)
        return lc

    def helper(self, root):
        # base case
        if not root:
            return 0, 0
        if not root.left and not root.right:
            return 1, 1

        left_lc, left_root_lc = self.helper(root.left)
        right_lc, right_root_lc = self.helper(root.right)

        root_lc = 1
        if root.left and root.left.val == root.val + 1:
            root_lc = max(root_lc, 1 + left_root_lc)

        if root.right and root.right.val == root.val + 1:
            root_lc = max(root_lc, 1 + right_root_lc)

        return max(root_lc, left_lc, right_lc), root_lc

Revelation:

• Extend function meaning. Stand at each level of recursion, think about what kind of info we need, and we can define our recursion function to return these info, sometimes, this info is not just one value, so we can let the function return what we need. If the recursion returns multiple values, we just need to think what is the base case, and in the each level recursion how to use these info.

Note:

• Time complexity = O(n), n is the number of nodes of the given tree. Because each node we just visited once.
• Space complexity = O(h), h is the height of the tree. Because the depth of the recursion is the height of the tree.

Solution: DFS

# 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
        """
        if not root :
            return 0

        max_len = 0
        stack = [(root, 1)]

        while stack:
            curr, l = stack.pop()
            max_len = max(max_len, l)

            if curr.left:
                new_l = l + 1 if curr.left.val == curr.val + 1 else 1
                stack.append((curr.left, new_l))

            if curr.right:
                new_l = l + 1 if curr.right.val == curr.val + 1 else 1
                stack.append((curr.right, new_l))

        return max_len

Revelation:

• This problem is also can be solved by BFS.

Note:

• Time complexity = O(n), n is the number of nodes of the given tree.
• Space complexity = O(n), n is the number of nodes of the given tree.